백준 15989 자바 - 1, 2, 3 더하기 4 (BOJ 15989 JAVA)

https://www.acmicpc.net/problem/15989

 

  처음엔 무지성 DP 돌리면 될줄 알았는데, 수의 순서가 다른 것은 하나로 처리해야 한다.

무작정 dp 진행하며 모든 쌍을 확인하고, 그 중 겹치는 것을 확인하기엔 메모리가 부족해보인다.

 

풀이1. 2차원 DP

https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/15900/BOJ_15989_2D-DP.java

 

  우선 서로 겹치는 쌍이 생기지 않도록 하려면 어떻게 해야할까? 각 n에서 더해지는 숫자에 제한을 두면 된다. 예를 들어 서로 겹쳐도 된다고 생각하고 n = 1~4 일 때 1,2,3의 덧셈으로 표현 가능한 경우를 보자.

1 : 1

2 : 2, 1+1

3 : 3, 1+1+1, 1+2, 2+1

4 : 1+1+1+1, 2+1+1, 1+2+1, 3+1, 1+1+2, 2+2, 1+3

이렇게 있다.

여기서 겹치는 경우들 (1+2와 2+1 / 2+1+1과 1+2+1, 1+1+2 / 1+3과 3+1)을 모두 하나만 남기려면, 뒤에 더해지는 수가 이전수보다 크거나같아야 한다는 조건을 걸면 된다. 그럼 1+2 / 1+1+1 / 1+3만 남게되고 겹치는 경우가 없다.

 

  이걸 어떻게 처리해야할까? 이런 경우 보통 DP를 2차원으로 확장하고 정의를 잘하면 풀리는 경우가 많다. dp[a][b]에서 a를 n, b를 현재 더해진 수라고 정의하면 된다. (1+1+2 라면 현재 +2를 한 것이므로 b가 마지막에 더해진 2가 된다.)

이렇게 정의하고 다음과 같이 계산한다.

dp[n][1] = dp[n-1][1] -> n=6이면 1+1+1+1+1(+1)과 같은 경우 체크

dp[n][2] = dp[n-2][1] + dp[a-2][2] -> n=6이면 ..[1]은 1+1+1+1(+2), ..[2]는 2+2(+2)와 같은 경우 체크

dp[n][3] = dp[n-3][1] + dp[n-3][2] + dp[n-3][3] -> 마찬가지로 n=6이면 ..[1]은 1+1+1(+3), ..[2]는 1+2(+3), ..[3]은 3(+3)과 같은 경우 체크

 

  추가로 코드상의 chkMax와 같은 부분 처럼 여러 테스트케이스에 대해 이미 계산한 부분이라면 이전에 계산한걸 활용할 수 있도록 memoization 처리도 해주면 더욱 효율성 좋게 계산 가능하다.

 

 

풀이2. 1차원 DP

https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/15900/BOJ_15989_1D-DP.java

 

  그런데, 소스를 제출하고보니 내 코드보다 더 짧은 시간으로 통과한 코드들이 있었다. 그래서 더 빠른 방법이 있을꺼라 생각되어 좀 더 생각해봤다. 결론적으로 보면 점화식을 추가해서 1차원 DP로 변경하여 더 빠르게 계산할 수 있었다. 전체에 대한 점화식도 가능할 것 같긴하지만, 내 수학적 지식이 좀 딸려서 전체에 대한 점화식은 무리였고 그냥 그려보고 보니 규칙이 발견된 경우이다.

 

  일단은 2차원 DP 풀이를 그려봤다. row는 풀이1의 dp[a][b]의 b를 뜻한다. column은 a를 뜻한다.

  그럼 규칙은 다음과 같다.

첫번째 row는 무조건 1이다.

두번째 row는 n이 4이상부터 n/2(내림) 이다.

세번째 row는 규칙성이 어느정도 있는듯 보였으나, 점화식을 구하긴 좀 어렵다고 판단했다.

 

따라서 세번째 row에 대해서만 dp를 진행하는 방식으로 변경해봤다. (calc 함수 참조)

이번엔 10000개에 대해 미리 구하고, 입력 들어온걸 바로바로 출력하는 형식으로 했다.

 

최종적으로 풀이1은 252ms, 풀이2는 92ms가 걸렸다.