코드업 5120

이번 문제는 코드업 5120 : codeup vs koistudy (Tiny) 이다.

https://codeup.kr/problem.php?id=5120

codeup vs koistudy (Tiny)

이전에 올렸던 코드업 5121과 유사한 문제이나 조건이 다르다.

입력으로 주어지는 N의 범위가 다르다.

입력으로는 첫 줄에 문제를 해결하는 총 일 수 인 정수 N 이 입력된다. (2<=N<=20)

다음 두 줄에 걸쳐 각각의 사이트에서의 실력치가 입력된다. (1<=실력치<=1000)

출력으로는 위 조건을 만족하면서 최대로 얻을 수 있는 실력치의 합을 한 줄로 출력한다.

 

이 문제를 먼저 해결한 후 5121번을 해결하였으므로 5121번의 풀이로도 해결이 가능하나, 이 문제에선 좀 더 단순한 방식을 사용하여 해결하였다. 코드는 짧은 대신 시간이 더 오래 걸린다. 재귀함수를 활용하여 모든 경우를 생각해주었다.

 

코드는 이러하다.

day = int(input())
code = list(map(int, input().split()))
study = list(map(int, input().split()))

result = 0

def level(date, cnum, snum, value):
    global result
    
    if day <= date:
        if cnum != 0 and snum != 0:
            result = max(result, value)
        return

    for i in range(2):
        if i == 0:
            value += code[date]
            cnum += 1
            level(date + 1, cnum, snum, value)
            value -= code[date]
            cnum -= 1
        elif i == 1:
            value += study[date]
            snum += 1
            level(date + 1, cnum, snum, value)
            value -= study[date]
            snum -= 1

level(0, 0, 0, 0)           
print(result)

 

day, code, study는 입력값을 저장해주는 변수들이다. result는 최댓값을 저장해두는 변수이다.

level이라는 함수를 정의하고 파라미터로 date, cnum, snum, value를 전달해 주었다. date는 현재 날짜, cnum은 code가 얼마큼 사용됐는지, snum은 study가 얼만큼 사용됐는지, value는 현재까지 더 해진 값을 의미한다.

만약 day가 date보다 작거나 같다면 끝까지 탐색했음을 의미하고 이 경우 만약 cnum과 snum 모두 0이 아닐 경우 value와 기존의 result를 비교하여 최댓값을 result에 새로 저장한다.

2가지 경우에 대해 반복문을 진행하는데 첫째로 code를 사용하는 경우, 둘째로 study를 사용하는 경우이다. code를 사용하는 경우 value에 code[date]를 더하고 cnum을 증가시킨다. 이후 함수를 다시 호출하여 재귀적으로 진행한 후 호출한 함수가 return 되었을 때 이전에 더했던 값을 빼주어 code를 사용하지 않은 경우로 돌려놓는다. study의 경우도 마찬가지로 진행하게 된다.

level을 호출하여 기본값으로 0을 모두 전달해준 뒤 값을 출력해주어 마무리한다.

(코드 길이: 729 byte(s) / 수행 시간: 975 ms / 메모리: 33780 kb)

 

이후 문제인 5121이전에 동일 문제 다른 조건에 대한 해결법을 생각해보게 하는 문제였다.