전체 글

[백준] 14500번 - 테크로미노 (!) (JAVA) [접근 방법] 브루트포스 파트이기에 모든 경우의 수를 탐색해야 한다는 것은 알고있었다. 어떻게 탐색 할 것인가? 가 가장 어려웠다. 첫번째로 고려한 방법은 모든 경우를 일일이 생각하여 구현하는 방법이다. (i , j)를 시작으로 하는 모든 경우의 수를 전부 고려한 후, 그중 최댓값을 구해서 N X M 보드의 모든 칸의 최대값을 비교하여 갱신할 계획이였다. worst case = 500 * 500 * 13 = 3,250,000 으로 시간도 적합했다. 그러나 너무나 까다롭고 귀찮은 구현에 포기하였다. 두번째 고려한 방법은 다른 사람들의 풀이 방법을 보고 풀었다. 위 4가지 도형은 상하좌우 완전 탐색으로 구현하고, 이 모형만 따로 구현하는 방법이다. 탐색..

[백준] 6064번 - 카잉 달력 (!) (JAVA) [접근 방법] 브루트포스 알고리즘 파트이기에, 1년 부터 M, N의 최소 공배수 까지 모두 탐색하고자 하는 것을 생각하였지만, 이는 시간 제한에 막히게 되었다. 실행 시간 1초 = 약 2000만번 연산 (1 ≤ M, N ≤ 40,000, 1 ≤ x ≤ M, 1 ≤ y ≤ N) worst case : M = 39983, N = 40_000 을 모두 탐색하는 경우 (39983은 소수) 39983 * 40000 = 약 16억 (X) 따라서 다른 방법을 찾아야 한다. 구하고자 하는 x을 고정 시키고 i를 +M 만큼 증가 시키며, y를 탐색하는 방법을 채택하게 되었다. 나머지 연산을 이용할 것인데, 이때 0이 나오는 것을 방지하기 위해 , x = x-1, y ..

[백준] 1748번 - 수 이어 쓰기 1 (!) (JAVA) [접근 방법] - 문제를 이해하자. 첫번째로 읽었을 때, 문제가 잘 이해 되지 않았다. N = 5 인 경우를 예로 들었을 경우, 123454321... 과 같이 이전 자리수와 연결되어 있기만 한 수도 가능한 것 인가? 라고 생각했다. 그러나 N = 15를 예로 든다면, 1/2/3/4/5/6/7/8/9/10/11/12/13/14/15 (/는 이해를 위해..) 와 같이 1 ~ N 까지 수를 그대로 뒤에 이어 붙인 것이다. - 어떻게 풀지 생각해보자. N = 120인 경우, 1 ~ 9 까지는 +1을, (한자리수) 10 ~ 99 까지는 +2를, (두자리수) 100 ~ 120 까지는 +3을 하면 된다. (세자리수) 이렇게 구현하기 위해서는 1 ~ 100..

[백준] 1107번 - 리모컨 (!) (JAVA) [접근 방법] 어떻게 접근해야 할까? 에 대한 대답은 쉽게 찾아 내었다. 부서진 번호가 포함되지 않은, N을 기준으로 가장 가까운 번호를 찾아내는 것이 관건 이었다. 브루트포스 알고리즘을 사용하여, 가능한 모든 채널 번호 부터 N까지 최소 누르는 수를 구하였다. 이동하려고 하는 채널인 N은 0 ~ 500_000 이지만, 9를 제외한 모든 버튼이 망가지는 경우, 999_999로 이동한 후, + / - 버튼을 눌러야 하므로, 0 ~ 999_999 까지의 수를 모두 고려하였다. [JAVA 코드] // 1476번 - 날짜 계산 import java.util.*; import java.io.*; public class Main { public static void..

[백준] 1476번 - 날짜 계산 (JAVA) [접근 방법] 처음엔 최대 공배수 문제라고 판단 하였지만, 예제 3번 E = 1(+15), S = 2(+28), M = 3(+19)의 최대 공배수를 계산 한 결과 "1680" 이 나오게 되었다. 브루트포스 알고리즘 방식으로 모든 경우의 수를 고려해야 한다. E, S, M 3개의 숫자 중 최댓값인 수를 제외하고 나머지 수를 각각 +15 +28 +19를 수행한다. 최종적으로 E = S = M을 만족하는 수 중 가장 작은 수를 출력한다. [JAVA 코드] // 1476번 - 날짜 계산 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) thro..

[백준] 2309번 - 일곱 난쟁이 (!) (JAVA) [접근 방법] 브루트포스 알고리즘 방식으로 모든 경우의 수를 고려해야 한다. 9명의 난쟁이 키의 합 중 2명의 키를 뺀 값이 100 인 경우를 찾아야 한다. 9개중 2개를 선택하여 빼는 모든 경우를 구현하고, 남은 7개의 합이 100이 되는 순간의 7개의 값을 정렬한 후 출력한다. [JAVA 코드] // 2309번 - 일곱 난쟁이 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { // 0. 입출력 선언 / 초기화 BufferedReader br = new BufferedReader(new I..