9184. 신나는 함수 실행
https://www.acmicpc.net/problem/9184
내 풀이 - 성공
from sys import stdin
import collections
dp = collections.defaultdict(int)
def w(a, b, c):
global dp
if (a, b, c) in dp:
return dp[(a, b, c)]
if a <= 0 or b <= 0 or c <= 0:
dp[(a, b, c)] = 1
elif a > 20 or b > 20 or c > 20:
dp[(a, b, c)] = w(20, 20, 20)
elif a < b and b < c:
dp[(a, b, c)] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
else:
dp[(a, b, c)] = w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)
return dp[(a, b, c)]
while True:
a, b, c = map(int, stdin.readline().split())
if a == -1 and b == -1 and c == -1:
break
print(f'w({a}, {b}, {c}) = ', end='')
print(w(a, b, c))while True 문을 돌려서 입력을 받고 a, b, c 모두 -1 일 때 break 하도록 함
재귀는 현재 조합의 값이 이미 구한 값이면 그 값을 사용하고
아니면 조건대로 재귀 돌려서 dp 값 구한 후,
최종적으로 dp 값 return
--
15649. N과 M (1)
https://www.acmicpc.net/problem/15649
내 풀이 - 성공
from sys import stdin
N, M = map(int, stdin.readline().split())
nums = [i for i in range(1, N+1)]
def func(n, comb):
if len(comb) == M:
for c in comb:
print(c, end=' ')
print()
return
for i in range(len(n)):
func(n[:i]+n[i+1:], comb+[n[i]])
func(nums, [])1 ~ N 까지의 숫자들을 nums 에 저장
재귀를 돌려서 현재 n 리스트에 있는 숫자들을 하나씩 comb 에 추가
이때 해당 숫자를 제외한 나머지 숫자들은 합쳐서 다음 n 으로 보내기
그러다 comb 의 길이가 M 과 같아지면 출력
15650. N과 M (2)
https://www.acmicpc.net/problem/15650
내 풀이 - 성공
from sys import stdin
N, M = map(int, stdin.readline().split())
nums = [i for i in range(1, N+1)]
def func(n, comb):
if len(comb) == M:
for c in comb:
print(c, end=' ')
print()
return
for i in range(len(n)):
func(n[i+1:], comb+[n[i]])
func(nums, [])15649. N과 M (1) 에서 재귀 돌리는 부분만 수정
현재 숫자보다 작은 값은 다시 추가할 필요가 없음
=> 그 조합은 이미 사용됐으므로
15651. N과 M (3)
https://www.acmicpc.net/problem/15651
내 풀이 - 성공
from sys import stdin
N, M = map(int, stdin.readline().split())
nums = [i for i in range(1, N+1)]
def func(n, comb):
if len(comb) == M:
for c in comb:
print(c, end=' ')
print()
return
for i in range(len(n)):
func(n, comb+[n[i]])
func(nums, [])15649. N과 M (1) 에서 재귀 돌리는 부분만 수정
중복으로 사용해도 되므로 슬라이싱 없이 n 리스트를 그대로 다음 재귀로 넘겨줌
15652. N과 M (4)
https://www.acmicpc.net/problem/15652
내 풀이 - 성공
from sys import stdin
N, M = map(int, stdin.readline().split())
nums = [i for i in range(1, N+1)]
def func(n, comb):
if len(comb) == M:
for c in comb:
print(c, end=' ')
print()
return
for i in range(len(n)):
func(n[i:], comb+[n[i]])
func(nums, [])15649. N과 M (1) 에서 재귀 돌리는 부분만 수정
중복으로 사용해도 되지만 비내림차순이어야 하므로
i 번째의 값을 포함해서 다음 재귀로 넘겨줌
=> 다음 수열의 값으로 i 이상의 값들만 오게 됨
Hello, World!