백준 1946 신입 사원

과정

• 1차원 배열을 만든다. 인덱스는 서류 심사 순위를 나타내도록 한다.
  • 서류 심사 순위에 대해 자동으로 정렬이 된 상태이다.
• 배열은 무조건 작아지는 경우만 세어 나가야한다.
• 배열을 순회하며 현재까지 나타난 최솟값을 저장해준다. 저장한 최솟값보다 더 작은 값이 나오면, 최솟값은 갱신, 선발 인원수는 +1을 한다.

시행착오

• 두 성적 순위는 모두 1위부터 N위까지 동석차 없이 결정된다고 가정한다.
  • 문제의 조건을 읽지 않아서 동석차 처리를 한참 고민했다.
• 입력은 점수가 아니라, 순위다. 1이 2보다 높은 것이다.
  • 점수로 생각해서 1 4, 5 5 가 입력으로 들어오면 5 5 를 선발하는 건 줄 알았다.
• 문제를 잘 못 읽고, 선발한 지원자가 조건을 만족하는 건 줄 알았다.
  • 조건을 만족하는 지원자만 선발하는 것이었음.
• 마지막에 가장 긴 감소하는 부분 수열 을 푼 코드를 사용했더니 시간 초과가 발생했다.
  • 부분 수열 전체를 구할 필요가 없다. 감소하는 최대 길이를 구하면 되는 것이었다.

import sys
tc: int = int(input())

for _ in range(tc):

    N: int = int(input())

    lst = [0] * N
    for _ in range(N):
        resume, interview = map(int, sys.stdin.readline().split())
        lst[resume - 1] = interview

    ans = 0
    interview_min = 1e9
    for i in range(N):
        if interview_min > lst[i]:
            interview_min = lst[i]
            ans += 1
            
    print(ans)

참고