0922_Algorithm_1946_신입사원

문제 : https://www.acmicpc.net/problem/1946

초기 구상과정

1. 서류 점수를 인덱스로 이용해서 면접 점수 저장
2. 서류 점수와 면접 점수가 1등이면 무조건 합격이라는 점
   3. 또 왜 이건 DP인가?

초기 코드

for tc in range(int(input())):
    N = int(input())
    dp = [0] * (N + 1)
    DtoI = [0] * (N + 1)
    for i in range(1, N + 1):
        Docu, Interview = map(int, input().split())
        DtoI[Docu] = Interview

    for rank1 in range(1, N + 1):
    	for rank2 in range(1, rank1):
            if DtoI[rank2] < DtoI[rank1]:
                break
        else:
            dp[rank1] = 1
    print(sum(dp))

• 초기코드에서 sample은 합격했으나 결국 시간초과..
• 시간초과를 해결하기 위한 대책들을 강구했다
  • input을 sys.stdin.readline으로 변경
  • 이중 for문을 어떻게든 단일 for문으로 변경

중간단계에서 이중 for문을 해결하고자 min함수를 사용해서 for문 하나를 줄여보자는 생각으로 코드를 변경했지만 이마저도 시간초과가 떴다.

    for rank in range(2, N + 1):
        if min(DtoI[:rank]) < DtoI[rank]:
            continue
        dp[rank] = 1

결론적으로는 min 역시 내부적으로는 for문을 사용하는 것과 마찬가지이기 때문에 시간초과를 해결하지 못했다.

최종 코드

import sys
input = sys.stdin.readline
for tc in range(int(input())):
    N = int(input())
    cnt = 1
    DtoI = [0] * (N + 1)
    for i in range(1, N + 1):
        Docu, Interview = map(int, input().split())
        DtoI[Docu] = Interview

    min_rank = DtoI[1]
    for rank in range(2, N + 1):
        if min_rank < DtoI[rank]:
            continue
        min_rank = DtoI[rank]
        cnt += 1
    print(cnt)

min을 사용하고나서 생각하니 굳이 계속해서 앞선 순위들을 체크할 필요 없이 가장 낮은 값의 순위(즉, 가장 높은 순위)를 찾아서 한 개만 저장해놓고 그것만을 비교해서 쓴다면 for문 하나를 줄일 수 있겠다고 생각해서 min도 지워버리고 min_rank만 계속해서 업데이트해서 쓰도록 변경했다. 또, dp 리스트를 만들고 리스트를 갱신하는 것보다 조건에 맞는 인원의 인덱스를 검증하는 것이 끝났다면 cnt를 업데이트하는 것이 sum함수를 쓰는 것보다 더 빠를 것이라고 생각해서 문제를 해결했다.

그래서 이게 왜 DP문제인가? 나는 왜 모르는가?