1학기 3주차 알고리즘 과제 (9095번 : 1, 2, 3 더하기)

9095번: 1, 2, 3 더하기 (acmicpc.net)

9095번: 1, 2, 3 더하기

 

 

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

 

 

📌내풀이

 

 

1차적으로 해당 문제를 접근한 방법이다.

 

그런데 단순히 이렇게 풀기에는 경우의 수가 너무 많음을 느꼈고, 배열이 다르다면 아래의 경우를 모두 다르게 보는 경우를 코드로 어떻게 표현해야할지를 고민했다.

 

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

 

 

그래서 경우의 수를 조금 고민해본결과 앞의 세수의 경우를 더한게 4번째 경우가 된다는 걸 알았다.

 

1 = 1[1]
2 = 1+1 , 2 [2]
3 = 1+1+1 , 2+1, 1+2 , 3 [4]
4 = [7]
.
.
.

 

그래서 해당 경우를 코드로 풀어내고자 조금 도움을 받았다.

 

만약 N에 대해서 경우의 수를 찾을 경우, 이 문제에서는 오직 1,2,3 만을 사용할 수 있으므로 다음 세가지 경우의 수가 있다.

 

1) (N-1) 에서 1더하기  ➡️ N-1을 만드는 경우의 수와 동일 =dp[N-1]

2) (N-2) 에서 2더하기  ➡️ N-2을 만드는 경우의 수와 동일 =dp[N-2]

3) (N-3) 에서 3더하기  ➡️ N-3을 만드는 경우의 수와 동일 =dp[N-3]

 

이러한 과정을 통해 코드를 구하면 다음과 같다.

 

 

코드

import sys
input = sys.stdin.readline
T = int(input())

for _ in range(T):
    N = int(input())
    dp = [0] * (N + 1)

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

    print(dp[N])

 

 

코드 설명

 

• 입력에 나와있듯 테스트 케이스의 개수를 나타내는 T를 입력받는다.
• 계단의 총 수 N을 입력 받는다.
• 길이가 N+1인 리스트 dp를 만들고, 이 리스트는 각 계단을 오르는 방법의 수를 저장한다.
• 1부터 N까지 각 계단을 오르는 방법의 수를 계산합니다.
• 만약 계단의 수가 1개라면, 한 가지 방법만 존재하고,
• 계단의 수가 2개라면, 1번째 계단을 오르는 방법과 2번째 계단을 오르는 방법 두 가지가 있다.
• 계단의 수가 3개라면, 1번째, 2번째, 3번째 계단을 오르는 방법 세 가지가 있습니다.
• 계단의 수가 3개 이상이라면, 마지막 계단을 오를 때 이전 계단에서 1계단 오른 경우, 2계단 오른 경우, 3계단 오른 경우의 수를 모두 더해야 한다.
• 계단을 모두 오른 후 마지막 계단에 도달하는 방법의 수를 출력하도록 한다.

 

해당 문제 역시 동적 계획법(Dynamic Programming)을 사용하여 풀어야했다.

아직은 낯선 코딩 방법? 이라 익숙해지려면 시간이 좀 걸릴 것 같고, 온전히 내힘으로 코드를 짜는 것에는 쉽지않음을 느낀다. 이렇게 여러가지 알고리즘 문제를 접하다보면 조금씩 실력이 늘 것이라 믿는다..

 

 

[ 참고한 자료 ]

 

[BOJ/백준] 9095번 1,2,3 더하기 (Python 파이썬) — great_park (tistory.com)

[BOJ/백준] 9095번 1,2,3 더하기 (Python 파이썬)