[조합+DFS] 6603번, 1182번, 9095번

1. 로또

링크 - https://www.acmicpc.net/problem/6603

코드

from itertools import combinations
import sys

input = sys.stdin.readline

while True:
    line = list(map(int,input().split()))
    
    if line[0]==0:
        break
    
    n = line[0]
    S = line[1:]

    answers = list(combinations(S,6))

    for answer in answers:
        for a in answer:
            print(a,end=" ")
        print()
    print()

combinations함수를 이용해서 풀어줬다.

2. 부분수열의 합

코드

from itertools import combinations
import sys

sys.setrecursionlimit(10**6)

input = sys.stdin.readline

n,s = map(int,input().split())

line = list(map(int,input().split()))

#원소 하나가 s랑 같을 때 
count = line.count(s)
if len(line)>=2:
    for i in range(2,len(line)+1):
        answers = list(combinations(line,i))
        for answer in answers:
            if s == sum(answer):
                count+=1

print(count)

combinations 함수를 이용해 풀어주었다. 2

3. 1,2,3 더하기

코드 - dfs

import sys
input = sys.stdin.readline
count=0
def dfs(curr,goal):
    global count  
    if curr==goal:
        count+=1
        return 
    for i in range(1,4):
        if curr+i<=goal:
                dfs(curr+i,goal)

t = int(input())
for i in range(t):
    n = int(input())
    dfs(0,n)
    print(count)
    count=0

처음에는 dfs로 풀었다.

코드 - dp

import sys

input = sys.stdin.readline

t = int(input())

for i in range(t):
    n = int(input())
    dp=[0]*(n+1)
    
    dp[1]=1
    if n>=2:
        dp[2]=2
    if n>=3:
        dp[3]=4
    
    if n>3:
        for j in range(4,n+1):
            dp[j] = dp[j-1]+dp[j-2]+dp[j-3]
    
    print(dp[-1])

dp로 푼 사람들도 많아서 dp로도 풀어보았다.

추가 - 조합 구현하기

def gen_combinations(arr, n): 
	result =[] if n == 0: 
    	return [[]] 
        
        for i in range(0, len(arr)): 
        	elem = arr[i] rest_arr = arr[i + 1:] 
            for C in gen_combinations(rest_arr, n-1): 
            	result.append([elem]+C) 
                
        return result

출처: https://cotak.tistory.com/70 [Pool's Taek]