문제
똑같은 문제가 프로그래머스에도 있었다. 예전에 풀었던 기억이 있는데 그 때는 처음에 접근할 때 DP를 사용하지 않는 방법을 사용했던 것 같다. 링크에 들어가보니 맞다^^;;
풀이
이번엔 바로 DP로 접근해서, 부분값을 새로운 값으로 어떻게 연결시킬지를 먼저 생각해보았다. 그림을 직접 연습장에 그려서 보니 아래와 같은 규칙을 발견할 수 있었다.
2xi타일을 채울 때,
- 맨 끝에
2x1막대 한 개를 추가하면 나머지2x(i-1)을 채우는 경우의 수를 세야 한다. 이것은dp[i-1]의 값과 같다.- 맨 끝에
1x2막대 두 개를 추가하면 나머지2x(i-2)를 채우는 경우의 수를 세야 한다. 이것은dp[i-2]의 값과 같다.
부분합을 활용하기 위해서는 맨 왼쪽이나 맨 오른쪽 끝에 막대를 추가하는 방식으로 가야 한다. 중간에 끼워 넣으면 중복이 생기고 부분합을 활용할 수 없기 때문이다. 기존의 블록 조합에 막대를 하나 갖다 붙이는 것이 중복되지 않은 새로운 블록 조합을 만드는 방법이다.
따라서 dp[i] = dp[i-1] + dp[i-2]라는 점화식을 세울 수 있다.
이를 바탕으로 작성한 코드는 아래와 같다.
코드
import java.io.*;
public class Main {
private static final int MAXIMUM = 1000;
private static final int MOD = 10007;
private static int n;
private static int[] dp = new int[MAXIMUM + 1];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
n = Integer.parseInt(br.readLine());
dp();
bw.append(String.valueOf(dp[n]));
br.close();
bw.close();
}
private static void dp() {
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++)
dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
}
}저번에는 각 n마다 하나하나 경우의 수를 센 다음 숫자들에서 피보나치를 우연히 발견한 것이었다. 하지만 이번엔 그림에서 명확히 보이는 규칙을 찾아내서 점화식을 세운 것이고, 그것이 우연찮게 피보나치가 된 것이다. 이번에 푼 방식이 훨씬 DP답고 효율적이었던 것 같다. 쉬운 문제지만 일단 만족만족.
