본문 바로가기
PS/BOJ

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

by Nahwasa 2021. 10. 4.

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가 걸렸다.

댓글