[백준][DP] 1946번 신입 사원 python (200926)

 

1. 문제 설명 

 

www.acmicpc.net/problem/1946

1946번: 신입 사원

 

 

2. 풀ㅇㅣ

1) 나의 기나긴 풀이

 

우선 문제 이해를 하는게 조금 어려웠는데 (예제 설명도 안되어있음 ㅜㅠ) 

 

합격자들의 조건은 상대방보다 두점수가 낮지 않음 이다. 

핵심은 A 지원자 두 영역 점수 모두가 B 지원자 두 영역 점수보다 클 경우에는

A, B 둘 중 하나만 합격리스트에 들어간다고 이해하면됨 

그리고 여기서는 합격 인원을 최대로 할수 있는 경우에 대해 물었으니  

A, B 중에서 더 큰 점수인 A 지원자를 떨어트린다 (점수가 큰 사람이 합격을 못하는 이상한 상황) 

 

예제 중 첫번째 경우를 살펴보면 

5

3 2

1 4

4 1

2 3

5 5

여기 5명 지원자중 합격을 못하는 사람은 5 5 가 되어야,

나머지 지원자들은 조건 (상대방보다 두점수가 낮지 않음) 에 맞아서 합격 리스트에 들어갈 수 있다. 

 

 

이 컨셉을 이해하고 코드 조건문을 세워보자면,  

우선 정렬은 불가피했다.. 나의 경우에는... 

def solution():
    N = int(sys.stdin.readline())
    num_list = []
    for idx in range(N):
        p, i = map(int,(sys.stdin.readline().split()))
        num_list.append((p, i))

    num_list = sorted(num_list)
    count_chk = 0

    for idx, one_score in enumerate(num_list):
        p_score,i_score = one_score
        if idx == 0:
            max_p, max_i = (p_score,idx), (i_score,idx)
            count_chk += 1

        else:
            if p_score > max_p[0]: # 입력된 p가 더 큰 경우
                max_p_idx = max_p[1]
                if i_score <= num_list[max_p_idx][1]: # 그 당시에 i score 도 가져오기 - i는 입력 숫자가 작은경우 p만 업데이트
                    count_chk += 1
                    max_p = (p_score, idx) # p update

            if i_score > max_i[0]: # 입력된 i가 더 큰 경우
                max_i_idx = max_i[1]
                if p_score <= num_list[max_i_idx][0]: # 그 당시에 p score 도 가져오기  - p는 입력 숫자가 작은경우 i만 업데이트
                    count_chk += 1
                    max_i = (i_score, idx) # p update

    return count_chk

exec_num = int(input())
for _ in range(exec_num):
    print(solution())

1) 먼저 점수들을 입력시키고 정렬한다. --> 작은 값이 먼저 나오도록 

2) 하나씩 탐색하면서 서류 점수(p_score)와 면접 점수를(i_score)를 확인하고,

    이때 가장 큰 서류점수, 가장 큰 면접 점수를 각각 max_p, max_i 로 저장해두는 컨셉으로 간다. 

        (** 그리고 인덱스까지 같이 넣어줘야함) 

 

3) 만약 이전에 나온 서류점수중 가장 큰 점수 max_p 보다 지금 입력된 서류점수(p_score) 가 더 크면 

        max_p 당시 인덱스를 통해 그때의 면접 점수도 확인한다 

         ---> max_p 당시 면접점수보다도 지금 입력된 면접점수(i_score) 가 크면 

                  입력된 면접, 서류 점수가 다 큰거니까 / 얘는 합격시키지 않는다. 

         ---> max_p 당시 면접점수보다도 지금 입력된 면접점수(i_score) 가 작으면 

                  합격리스트에 들어올수 있음 , 합격자수 +=1 해주고, max_p 값 업데이트 

 

4) 만약 이전에 나온 면접점수중 가장 큰 점수 max_i 보다 지금 입력된 면접점수(i_score) 가 더 크면 

        max_i 당시 인덱스를 통해 그때의 서류 점수도 확인한다 

         ---> max_i 당시 서류점수가 지금 입력된 서류점수(p_score) 가 크면 

                  입력된 면접, 서류 점수가 다 큰거니까 / 얘는 합격시키지 않는다. 

         ---> max_i 당시 서류점수가 지금 입력된 서류점수(p_score) 가 작으면

                  합격리스트에 들어올수 있음 , 합격자수 +=1 해주고, max_i 값 업데이트 

 

처음엔 min_i, min_p 로 해두려 했는데, 두가지 예제를 보고 

큰값을 빼주는 게 맞겠다 싶어서 최대를 저장하는 방식으로 풀었다. 

 

2) 다른 사람 풀이 - 깔끔 명료함 

suri78.tistory.com/196

[백준알고리즘] 1946번: 신입 사원 -Python

import sys
for _ in range(int(sys.stdin.readline())):
    n = int(sys.stdin.readline())
    score = sorted([tuple(map(int, sys.stdin.readline().split())) for _ in range(n)], key=lambda x:x[0])
    p, ans = n+1, 0
    for s, e in score:
        if p > e:
            ans += 1
            p = e
    sys.stdout.write("{}\n".format(ans))

 

오름 차순으로 정렬해준것 가진 똑같은데, 

그 이후에는 굳이 나처럼 복잡하게 풀지 않고 

하나의 등수가 자신보다 낮은 사람들 중 최대로 뽑히는 사람의 수에 +1 을 한 것이다. 

 

가령 첫번째꺼는 이렇게 정렬이 되는데 

[(1, 4), (2, 3), (3, 2), (4, 1), (5, 5)]

서류점수 1을 기준으로 해서 뒤에나오는 서류점수 1보다 큰 친구들 중에서

면접점수 4보다 낮은 사람들만 고르는거임.... 

 

 

이렇게 풀껄.... !