전체 글

[백준] 오르막 수 (11057번 JAVA) (!) / 401 - 다이나믹 프로그래밍 1 (연습) [접근 방법] * N자리의 수이고 끝자리가 K 인 오르막 수의 개수는 "N-1 자리의 수이고 끝자리가 0~K 인 오르막 수의 개수를 모두 더한 것" 과 같다. 즉, N 자리수의 오르막 수의 총 개수는 N 자리수 이고 끝자리가 각각 0 부터 9 까지의 경우의 수를 모두 더한 것을 구하면 된다. N이 5인 경우를 예로 들겠다. 5자리수이고 끝자리 수가 5인 오르막 수의 경우의 수를 구하는 과정이다. 4자리 수이고 끝자리 수가 0 부터 5인 각각의 경우를 모두 더한 것과 같다. 5자리 수의 끝자리 수가 5인 경우를 위와 같이 구했다면, 5자리 수의 오르막 수를 모두 구하기 위해선 끝자리가 0 ~ 9 인 경우를 모..

[백준] 동물원 (1309번 JAVA) / 401 - 다이나믹 프로그래밍 1 (연습) [접근 방법] 우리의 크기가 2*i 인 배열에 사자를 배치하는 경우의 수를 저장한 배열 DP[i] 라 할때, DP[1] = 3 DP[2] = 7 DP[3] = 17 DP[4] = 41 DP[0] = 1이라 하면, (i >= 2) 에 대하여, DP[i] = DP[i-1] * 2 + DP[i-2] 가 성립한다. 너무 때려 맞춘 느낌이 강하게 들어서 기분이 좋진 않다. [JAVA 코드] import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java..

[백준] RGB거리 (1149번 JAVA) (!) / 401 - 다이나믹 프로그래밍 1 (연습) [접근 방법] 첫 번째 집을 칠하는 경우에 따라 모든 경우를 전수조사 해야한다. 전수조사 를 해야 한다는 것이 가장 중요! 1. 첫 번째 집을 빨간색 으로 칠하는 경우 2. 첫 번째 집을 초록색 으로 칠하는 경우 3. 첫 번째 집을 파란색 으로 칠하는 경우 1, 2, 3 방법 중 최솟값을 선택 [JAVA 코드] 1. N번째 집부터 1번째 집까지 Top-Down 방식 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io..

[백준] 합분해 (2225번 JAVA) (!) / 400 - 다이나믹 프로그래밍 1 [접근 방법] 표를 이용하여 경우의 수를 정리 해 보았다. 여기서 발견할 수 있는 규칙은 21 + 35 = 56 으로 도출된다는 것이다. 왼쪽 칸 + 위쪽 칸 = 현재 칸의 규칙을 가지고 있다. 이를 DP의 점화식으로 정리한다면, DP[N][K] = DP[N][K-1] + DP[N-1]+[K] (1

[백준] 제곱수의 합(1699번 JAVA) (!) / 400 - 다이나믹 프로그래밍 1 [접근 방법] 배열 DP 는 해당 인덱스를 제곱수의 합으로 나타낼 때, 그 제곱수 항의 최소 개수를 저장한다. 13을 예로 들겠다. 13 = 3^2 + 2^2 인 경우 항이 개로 최소 개수는 '2' 가 된다. (13 - 1^2) , (13 - 2^2) , (13 - 3^2) 중 제곱수 항의 최소 개수 + 1 과 같다. 12 의 제곱수 식에 (+ 1^2) 를 하는 경우 9 의 제곱수 식에 (+ 2^2)를 하는 경우 4 의 제곱수 식에 (+3^2)를 하는 경우 중 최소항의 개수를 가진 것을 고르면 된다. (4^2 > 13 이므로 제외된다.) [JAVA 코드] import java.io.BufferedReader; impo..

[백준] 연속합 (1912번 JAVA) (!) / 400 - 다이나믹 프로그래밍 1 [접근 방법] 문제 고민에 굉장히 많은 시간을 소요하였다. "DP 문제는 모든 것을 내가 구현할 필요는 없다." 라는 것을 다시끔 일깨워 준 문제 였다. 즉, 예제 1번 처럼 [10, -4, -3, 1, 5, 6, -35, 12, 21, -1] 이 주어지는 경우 직접 프로그래밍으로 어느 지점의 연속된 수의 합이 최대값 인지를 구할 필요가 없다는 것이다. '음수가 나오는 경우' , '음수 뒤에 양수가 나와서, 둘다 더하는 것이 이득인지 아닌지' 등 복잡한 경우들을 직접 고려하여 해결할 필요는 없는 것이다. 그냥 방법만 알려주고, 놓고 온다는 표현이 적절할 것 같다. for(int i=1; i