[Baekjoon/백준] 수 분해_ 1437

공부를 다시 시작하자!👸🏻

 

1437번: 수 분해

문제 설명

음이 아닌 정수 N을 한 개 이상의 음이 아닌 정수의 합으로 나타낼 때, 이를 "N을 분해한다"라고 부르자.

예를 들어, 4 = 1+1+1+1 = 1+1+2 = 1+3 = 2+2 = 4로 나눌 수 있다.

분해 곱이란 N을 분해해서 나타난 수들을 전부 곱한 것을 의미한다. N=4일 때, 분해 곱은 다음과 같다.

• 4 = 1+1+1+1, 곱 : 1*1*1*1 = 1
• 4 = 1+1+2, 곱 : 1*1*2 = 2
• 4 = 1+3, 곱 : 1*3 = 3
• 4 = 2+2, 곱 : 2*2 = 4
• 4 = 4, 곱 : 4*1=4

입력

첫째 줄에 음이 아닌 정수 N이 주어지고 N은 1,000,000보다 작거나 같다.

 

출력

숫자가 너무 클 것을 대비하여 10007로 나눈 나머지를 출력한다.

 

 

풀이 방법

0= 0 ,곱 0*1=0

1= 1 ,곱 :1*1=1

2= 2 ,곱 :2*1=2

3= 3 ,곱 :3*1=3

4= 4 ,곱 :4*1=4

5= 2+3 ,곱 :2*3=6

6= 3+3 ,곱 :3*3=9

7= 3+2+2 ,곱 :3*2*2=12

8= 3+3+2 ,곱 :3*3*2=18

9= 3+3+3 ,곱 :3*3*3=27 

 

0~9까지 연산을 하나하나 적용하니 5부터는 분해할 때 3이 들어가야 한다는 규칙이 보였다.

그래서 6부터는 arr[index]=arr[index-3]*3 이라는 점화식을 이용하여 문제를 해결하였다.

 

왜?

규칙이 있고 점화식으로 푸는 게 가능하기 때문에 DP가 최선이라고 생각했고 N의 숫자가 생각보다 크기 때문에 한 번의 연산만으로 푸는 것이 좋기 때문에 해당 방법을 사용하였다.

 

코드

n=int(input())# 입력

dp=[0]*1000001 # N이 입력받을 수 있는 숫자+1 만큼 선언

dp[1]=1 #예외적인 부분들은 미리 선언
dp[2]=2
dp[3]=3
dp[4]=4

for i in range(5,n+1):
    dp[i]=(dp[i-3]*3)%10007 #점화식 적용

print(dp[n])