[코딩 테스트 연습(파이썬/Python)] 백준 9095번 _ 1,2,3 더하기

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

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) 1을 만드는 방법은 1, 2를 만드는 방법은 2, 3을 만드는 방법은 4이다.

2) 이를 이용해 4를 만들 때는 1 + 3 or 2 + 2 or 3 + 1 셋 중 하나의 방법으로 만든다.

3) 예시를 살펴보면 더하는 순서가 다르면 다른 방법으로 센다.

4) 즉 4를 만드는 방법의 수는 이전 세 개의 숫자를 만드는 방법(1,2,3)의 합과 같다.

5) 모든 숫자를 만드는 방법의 수는 이전 세 개의 숫자를 만드는 방법의 수의 합과 같다.

 

# 정답
T = int(input())
for _ in range(T):
    tmp = [1,1,2,4]
    n = int(input())
    if n <= 3:
        print(tmp[n])
    else:
        tmp += ((n -3) * [0])
        for j in range(4, n+1):
            tmp[j] += sum(tmp[j-3:j])
        print(tmp[-1])

솔직히 아직도 백준의 입력 받는 방식을 잘 이해를 못하겠다. 언제는 입력이 한 번에 주어지고, 언제는 차례로 주어지고,, 입력 받는 방식 때문에 계속 틀리고 1,2,3의 경우를 고려하지 않아 또 틀리기도 했다;

 

import sys
T = list(map(int, sys.stdin.readlines()))
for n in T[1:]:
    tmp = [1,1,2,4]
    if n <= 3:
        print(tmp[n])
    else:
        tmp += ((n -3) * [0])
        for j in range(4, n+1):
            tmp[j] += sum(tmp[j-3:j])
        print(tmp[-1])

이제야 좀 이해를 한 것 같은데, 다음과 같이 한 번에 모든 입력을 받거나,

import sys
T = int(sys.stdin.readline())
for _ in range(T):
    n = int(sys.stdin.readline())
    tmp = [1,1,2,4]
    if n <= 3:
        print(tmp[n])
    else:
        tmp += ((n -3) * [0])
        for j in range(4, n+1):
            tmp[j] += sum(tmp[j-3:j])
        print(tmp[-1])

위처럼 한 줄 한 줄 입력을 받아오며 해결할 수도 있다.

import sys  
T = int(input())  
N = [int(sys.stdin.readline()) for i in range(T)]
for n in N:
    tmp = [1,1,2,4]
    if n <= 3:
        print(tmp[n])
    else:
        tmp += ((n -3) * [0])
        for j in range(4, n+1):
            tmp[j] += sum(tmp[j-3:j])
        print(tmp[-1])

맨 처음 입력으로 몇 줄을 받아올 지 설정한 뒤 가져오는 것도 가능하다.