섹션 7. 휴가

---

내 코드1

n = int(input())

schedule = []
for _ in range(n):
    T, P = map(int, input().split())
    schedule.append((T, P))

res = 0


def dfs(now, p_sum):
    global res
    if now > n:
        return
    if now == n:
        res = max(res, p_sum)
        return

    t, p = schedule[now]
    dfs(now + t, p_sum + p)
    #현재 상담을 안하기로 한 경우
    dfs(now + 1, p_sum)


dfs(0, 0)
print(res)

now가 n보다 클 때 return하는 종료조건을 추가한 코드이다.

채점기도 통과했지만 논리적으로 맞지 않는다고 생각한다.

 

마지막 상담을 실시했을 때 휴가일을 포함하게 된다면 res에 갱신 없이 함수를 종료하게 되는데 만약 이전 상담까지의 p의 합이 최대값 즉, 정답이 된다면 틀리게 되기 때문이다.

 

어쨌든 테스트 케이스 수가 적어서 운좋게 통과했다고 생각함.

 

내 코드2

n = int(input())

schedule = []
for _ in range(n):
    T, P = map(int, input().split())
    schedule.append((T, P))

res = 0


def dfs(now, p_sum):
    global res
    if now == n:
        res = max(res, p_sum)
        return

    t, p = schedule[now]
    if now + t > n:
        if now + 1 >= n:
            res = max(res, p_sum)
            return
        else:
            dfs(now + 1, p_sum)
    else:
        # 현재 상담을 하기로 한 경우: now + t로 넘어감
        dfs(now + t, p_sum + p)
        # 현재 상담을 안하기로 한 경우
        dfs(now + 1, p_sum)


dfs(0, 0)
print(res)

내 코드1에서 정답 처리를 받고 찜짐해서 수정한 코드이다.

 

 

해설

n = int(input())

schedule = []
for _ in range(n):
    T, P = map(int, input().split())
    schedule.append((T, P))

res = 0


def dfs(now, p_sum):
    global res
    if now == n:
        res = max(res, p_sum)
        return

    t, p = schedule[now]
    if now + t <= n:
        # 현재 상담을 하기로 한 경우: now + t로 넘어감
        dfs(now + t, p_sum + p)
    # 현재 상담을 안하기로 한 경우
    dfs(now + 1, p_sum)


dfs(0, 0)
print(res)

내 코드2와 논리는 거의 비슷하나 중복되는 코드도 없이 효율적으로 잘 짰다고 생각한다.

내 코드2 보다 해설코드를 레퍼런스로 하자.

 

설명

now + t <= n일 때만 상담을 하는걸로

현재 상담을 안하는 건 종료조건: now==n일 때까지 계속해준다.

 

 

피드백

주어진 상담 예약일정에서 휴가를 침범하는 예약은 없다고 생각한게 잘못됐다.

이 생각 때문에 다 짜놓고 정답처리를 받을 수 없었다.

예제에서 위 반례를 제시해주지 않아 휴가 침범은 없다고 단정지었는데

그래도 생각을 좀 더했고 이전 생각이 잘못된 것이란 걸 알아차렸기 때문에 끝내 정답을 받을 수 있었다.

 

지금까지의 문제 풀이에서는 이렇게 반례를 생각해보는 연습이 부족했다고 생각한다.

 

기업 코딩테스트에서는 종종 히든 케이스를 숨겨놓아 통과처리를 받아도 틀려버리는 경우가 있다고 한다.

내 생각엔 이 문제의 반례처럼 사소한 요소들을 캐치하지 못하면 변별당할 수 있다고 보며 또한 문제를 거의 다 풀어놓고 정답처리를 받지 못하는 경우도 발생할 수 있다고 생각한다.

 

아무튼 이번에 머리를 굴려서 논리적 오류를 찾아낸 건 잘했고 항상 반례가 숨어져 있을지 생각해보는 연습을 의식적으로 할 필요가 있겠다.