[백준] 재귀함수 사용하기

가능한 경우, 불가능한 경우, 이외의 경우 셋으로 나눠서 설계하자

1,2,3 더하기

해당 문제는 재귀를 모를 당시에는 정말 어려웠는데,, 이제는 왜 그렇게 푸는지도 이해가 되고, 어떻게 풀어야할지도 이해가 어느정도는 된다. 신기하다. 하면 할수록 느는 것인디 왜 그렇게 하기싫어했을까.

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

def solution(sum, goal):
    ans = 0
    if sum > goal:	# 1. 불가능한 경우
        return 0
    if sum == goal:	# 2. 정답인 경우
        return 1
    # 3. 이외의 경우
    ans += solution(sum+1,goal)
    ans += solution(sum+2,goal)
    ans += solution(sum+3,goal)
    return ans


n = int(input())
for _ in range(n):
    goal = int(input())
    answer = solution(0,goal)
    print(answer)

1759번. 암호 만들기

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

def check(s):
    # 모음 : a e i o u
    ja, mo = 0, 0
    for el in s:
        if el == 'a' or el == 'e' or el == 'i' or el == 'o' or el == 'u':
            mo += 1
        else:
            ja += 1
    return mo >= 1 and ja >= 2


def solution(length, arr, sum, idx):
    if len(sum) == length:
        if check(sum):
            print(sum)
        return
    if idx >= len(arr):
        return
    solution(length,arr,sum+arr[idx],idx+1)
    solution(length,arr,sum,idx+1)


l, c = list(map(int,input().split()))
arr = list(input().split())
arr.sort()

solution(l,arr,"",0)

6603번. 로또

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

재귀문제를 풀때 조건만 잘 지켜주면 되는 것 같다. 불가능, 가능, 이외의 경우

그리고 트리를 생각하면 된다.

def solution(arr,lotto,idx):
    if 6 == len(lotto):
        print(' '.join(lotto))
        return
    if len(arr) <= idx:
        return
    solution(arr,lotto + [arr[idx]],idx+1)
    solution(arr,lotto,idx+1)


while True:
    arr = list(map(str,input().split()))
    if arr[0]=="0":
        break
    k, arr = arr[0], arr[1:]
    solution(arr,[],0)
    print()

1182번. 부분수열의 합

백준님과 약간 다른 방법, 기존에 강의하셨던 방법대로 풀이해보았다. 조건 맞추는걸 이해했다고 생각했는데 그렇지 않아서 생각보다 놀랐음.

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

def solution(arr,N,S,lotto,idx):
    if sum(lotto) == S and idx == N and len(lotto) != 0:
        return 1
    if len(arr) == idx:
        return 0
    ans = 0
    ans += solution(arr,N,S,lotto+[arr[idx]],idx+1)
    ans += solution(arr,N,S,lotto,idx+1)
    return ans


N,S = list(map(int,input().split()))
arr = list(map(int,input().split()))
answer = solution(arr,N,S,[],0)
print(answer)

14501번. 퇴사

global 문법에 대해 이해하게 된 시간

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

def solution(arr, s, idx):
    global ans
    if idx > len(arr):
        return
    if idx == len(arr):
        ans = max(ans,s)
        return
    solution(arr,s+arr[idx][1],idx+arr[idx][0])
    solution(arr,s,idx+1)
    return ans


N = int(input())
arr = []
ans = 0
for _ in range(N):
    arr.append(list(map(int,input().split())))
answer = solution(arr,0,0)
print(answer)

14888번. 연산자 끼워넣기

음수 나누기 

ans = -(-a // b)

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

def solution(N,arr,tmp,cal,idx,plus,minus,multi,div):
    global min_num,max_num
    if idx == N:
        if min_num > tmp:
            min_num = tmp
        if max_num < tmp:
            max_num = tmp
        return
    if sum(cal)==0:
        return
    if plus > 0:
        solution(N,arr,tmp + arr[idx],cal,idx+1,plus-1,minus,multi,div)
    if minus > 0:
        solution(N,arr,tmp - arr[idx],cal,idx+1,plus,minus-1,multi,div)
    if multi > 0:
        solution(N,arr,tmp * arr[idx],cal,idx+1,plus,minus,multi-1,div)
    if div > 0:
        if tmp >= 0:
            solution(N,arr,tmp // arr[idx],cal,idx+1,plus,minus,multi,div-1)
        else:
            solution(N,arr,-(-tmp // arr[idx]),cal,idx+1,plus,minus,multi,div-1)


N = int(input())
a = list(map(int,input().split()))
cal = list(map(int,input().split()))
min_num, max_num = 10**9, -10**9
solution(N,a,a[0],cal,1,cal[0],cal[1],cal[2],cal[3])
print(max_num,min_num)