코드업 5121

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

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

codeup vs koistudy (Small)

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

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

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

 

이전 문제(코드업 5120)은 이와 유사한 문제이나 N의 범위가 훨씬 작다. 즉, 같은 방법을 사용할 경우 시간 초과가 나게 된다. 이전 문제에 대한 포스팅은 추후에 하도록 하겠다.

새로운 방법으로 반복문을 하나만 사용하여 해결이 가능하도록 하였다. 생각해낸 방법은 새로운 list를 사용하여 실력치의 차이가 가장 적은 것을 저장하는 것이다. 이때 한 가지 조건이 더 필요한데, 상대적으로 작은 실력치를 가진 사이트의 해당 date에서 값이 가장 큰 값을 골라야 한다는 것이다. 

 

코드는 이러하다.

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

result = 0
date = 0
cnum = 0
snum = 0
carr = [0, 1001]
sarr = [0, 1001]
temp = 0

for date in range(day):
    if code[date] > study[date]:
        result += code[date]
        cnum += 1
        temp = code[date] - study[date]
        if date == 0:
            carr[0] = date
            carr[1] = temp
        elif carr[1] > temp and study[date] > study[carr[0]]:
            carr[0] = date
            carr[1] = temp
    elif code[date] < study[date]:
        result += study[date]
        snum += 1
        temp = study[date] - code[date]
        if date == 0:
            sarr[0] = date
            sarr[1] = temp
        elif sarr[1] > temp and code[date] > code[sarr[0]]:
            sarr[0] = date
            sarr[1] = temp
    elif code[date] == study[date]:
        temp = 0
        if cnum >= snum:
            result += study[date]
            snum += 1
            if date == 0:
                sarr[0] = date
                sarr[1] = temp    
            elif sarr[1] > temp and code[date] > code[sarr[0]]:
                sarr[0] = date
                sarr[1] = temp        
        else:
            result += code[date]
            cnum += 1
            if date == 0:
                carr[0] = date
                carr[1] = temp   
            elif carr[1] > temp and study[date] > study[carr[0]]:
                carr[0] = date
                carr[1] = temp
        
if snum == 0:
    result -= code[carr[0]]
    result += study[carr[0]]
elif cnum == 0:
    result -= study[sarr[0]]
    result += code[sarr[0]] 

print(result)

 

day, code, study를 통해 입력값을 저장한다.

result는 계산된 결과, date는 해당 날짜(굳이 선언할 필요 없음을 뒤늦게 깨달았다.), cnum과 snum은 해당 사이트가 몇 번 풀이됐는지, carr와 sarr는 앞서 말한 실력치 차를 저장하기 위한 list이다. temp는 차이를 임시로 저장하기 위해 선언하였다.

day 기간 동안 list들을 비교하여 진행하게 된다. 우선 code의 값이 study의 값 보다 큰 경우, result에 code[date]를 저장해주고 cnum을 1 증가시킨다. 이후, temp를 이용해 차이를 저장해둔다. 만약 첫날이라면 carr[0]에 date를, carr[1]에 temp를 저장해두어 기준치를 만들어둔다. 그렇지 않을 경우 만약 temp가 carr[1]보다 작고 study[date]가 study[carr[0]]보다 큰 경우 즉, 차가 더 작고 해당 date에서의 study의 값이 더 클 경우 carr[0]에 date를, carr[1]에 temp를 저장한다.

study의 값이 code의 값 보다 큰 경우에는 반대로 진행하면 된다.

만약 두 값이 작을 경우 temp 즉, 차이는 0이 된다. 만약 cnum이 snum보다 큰 경우 code의 문제를 더 많이 풀었음을 의미하고 snum을 더 풀 수 있도록(snum이 0이 아니도록 해야 하므로) study의 값을 더하고 위와 동일한 원리로 sarr를 설정해준다. snum이 cnum보다 큰 경우는 이와 반대로 진행하면 된다.

이제 snum이 0인 경우 기존에 저장해두었던 carr를 이용해 해당 index의 code값을 빼주고 study에서 더해 주어 study를 사용하게 한다. cnum이 0인 경우 반대로 진행하면 된다.

이후 결과를 출력해주면 된다.

(코드 길이: 1713 byte(s) / 수행 시간: 19 ms / 메모리: 34028 kb)

 

시간을 줄이기 위해 생각을 하느라 다소 애를 먹은 문제이다. 풀고 나니 불필요한 조건들도 보이고(특정 index에서 더 커야 한다는 것과 같은) 반복된 부분이 많아 보여 아쉽다. 좀 더 매끈하고 유연하게 풀 수 있도록 수정하고 더 빠르게 생각할 수 있도록 해야겠다.