[Python] 백준 9095번_1, 2, 3 더하기

문제 

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

9095번: 1, 2, 3 더하기

충요하다고 생각하는 키워드에 형광펜을 쳐 보았다.

특이점

1. 오직 1, 2, 3의 합으로만 표현 가능하다. 잊으면 안됨! (사실 내 얘기임)
2. 입력값은 특이하기 11 미만이라고 명시 해 놓았다. 따라서 범위는 0 < n < 11, n은 정수 이다.
3. 입력 케이스마다 바로 대응하여, 방법의 수(=값)을 출력해야 한다. 

코드

cnt = int(input())

for j in range(cnt):
    num = int(input())
    way = [0]*(num+1)

    for i in range(1, num+1):
        if i == 1:
            way[i] = 1
        elif i == 2:
            way[i] = 2
        elif i == 3:
            way[i] = 4
        else:
            way[i] = way[i-1] + way[i-2] + way[i-3]
    
    print(way[num])

풀이 

• n이 1=> 1, 2=>2, 3=> 4는 기본값으로 세팅해줘야 한다 (점화식 영향)
• n이 4=> 7, 5=> 13, 6=> 24, 7=> 44 값을 이용해 점화식을 도출할 수 있다.
  
  •  way[i] = way[i-1] + way[i-2] + way[i-3]
  • 경우의 수를 계산할 떄, 큰수 ~ 작은 수 순서대로 전개했는데, 그것보단 1+a 부터 진행하는게 규칙 찾기엔 더 용이하다. 
  • 예를들면, 5의 경우) 5 = 3+2 이게 아니라, 5= 1+1+1+1+1 이렇게 아래처럼 최소 단위의 합부터 시작하는 것이다.

           5 = 1 + 1 + 1 + 1 + 1 

              = 1 + 1 + 1 + 2 = 1 + 1 + 2 + 1 = 1 + 2 + 1 + 1

              = 1 + 2 + 2 

              = 1 + 1 + 3 = 1 + 3 + 1

              = 2 + 1 + 1 + 1 

              = 2 + 2 + 1 = 2 + 1 + 2

              = 2 + 3

              = 3 + 1 + 1

              = 3 + 2

• 점화식이  way[i] = way[i-1] + way[i-2] + way[i-3] 인 이유 
  • 계산 단위가 되는 수는 1, 2, 3이다. 따라서, n을 1 + a로 나눴을 때, 1로 시작하는 경우의 수는 a의 경우의 수와 동일하다고 볼 수 있다.
  • .다시 예를들어, n= 5일때
    • 5  = 1 + 4이다. 따라서 1로 시작하는 경우의 수는 way[4]의 값과 동일하다.
    • 5 = 2 + 3이다. 따라서 2로 시작하는 경우의 수는 way[3]의 값과 동일하다.
    • 5 = 3 + 2이다. 따라서 3으로 시작하는 경우의 수는 way[2]의 값과 동일하다. 
    • 그러므로 way[5]는 덧셈 단위인 1, 2, 3으로 시작하는 각각의 경우의 수의 합이므로 way[4], way[3], way[2]의 값을 더한 것과 동일하다. 
• 추가적으로, 문제의 입력과 출력이 일대일 대응이 되어 출력해야 하는 시스템이다.
  • 따라서 처음 입력값 == 입력 숫자 개수 --> 를 사용해 for문을 돌렸고, 그 안에서 1개씩 값을 받아와 경우의 수를 출력하도록 작성했다. 

 

다른 풀이 

 출처: https://www.acmicpc.net/source/18065262

N = int(input())
arr=[1,2,4]
for i in range(4,11):
    arr.append(sum(arr[-3:]))
for _ in range(N):
    T = int(input())
    print(arr[T-1])

→ 문제 조건에서, n은 양수이며 11보다 작다를 적극 활용한 케이스이다.

• 무조건 n이 11미만의 수에서 나올 것이므로 방법의 수를 11까지 미리 구해놓는다. 
  • 이러면 반복 작업도 적고 용량 차지도 덜 할것 같다..오
  • -1~-3까지의 값을 더하는 것을 sum(arr[-3:])로 나타냈다! 이러면 -3~ -1까지의 합을 구할 수 있겠다. 
• 방법의 수를 다 구해놓은 후, 테스트 케이스를 다시 활용해 for문을 돌려 입력값을 받고, 바로 출력한다.
  • 이러면 입력 - 출력 1대1 대응도 지킬 수 있다!