[코딩테스트] 1,2,3 더하기 - Python

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

 

from itertools import product 

N = int(input())
M = [int(input()) for _ in range(N)]

for k in M: 
    cnt = 0 # 정수 K를 1,2,3의 합으로 나타내는 방법 개수
    for i in range(1, k+1): # 1~k개의 중복 순열을 만든다...
        for j in product([1,2,3], repeat=i): 
            if sum(j)==k: # 각 조합의 합이 k면, 카운트
                cnt+=1
    print(cnt) # 개수 출력

 

하하 모든 경우의 수를 놓고 ... 조건에 만족하면 카운트 했더니 시간이 오래 걸리는 군.................

 

1개의 중복순열 -> [1],[2],[3]

2개의 중복순열 -> [1,1],[1,2],[1,3] **** [3,3]

.

.

.

n개의 중복순열 -> [1,1,1,1,1,1,1,1, .. 1] ~ [n,n,n,n,n,n ...n]

 

M의 값들이 11 이내라는 조건이 있었기에 정답이라고 나온 것 같다. . .

 

1~k 개가 아닌, k//3 개부터 k개의 중복 순열이라고 말해도 될듯 하다..

 

원래 답안

DP를 사용해야 한다..

f(i) = f(i-3) + f(i-2) + f(i-1) 의 공식을 알아내면 금방 풀 수 있는 문제이다!

코틀린으로 푸는 연습을 하자..!!

 

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()
 
    val dp = IntArray(11)
    dp[1] = 1
    dp[2] = 2
    dp[3] = 4
    for(i in 4..10) {
        dp[i] = dp[i-3] + dp[i-2] + dp[i-1]
    }
 
    val sb = StringBuilder()
    val testCase = br.readLine().toInt()
 
    repeat(testCase) {
        sb.append("${dp[br.readLine().toInt()]}\n")
    }
    
    bw.write("$sb")
    bw.flush()
    bw.close()
    br.close()
}