백준 algorithm study 1932 1946 11727 DP python

파이썬 알고리즘 : 신입사원, 정수 삼각형, 2xn 타일링 2

백준 1946 , 백준 1932, 백준 11727

2023년 9월 18일 알고리즘 문제풀이

문제 1 백준 1946

문제 링크

1차 시도

나의 생각

서류에서 1등을 한 사람의 면접 성적을 기준으로 삼았다. 이 기준보다 면접 성적이 높은 사람만 합격할 수 있다. 기준보다 면접 성적이 낮은 사람은 서류 성적도 당연히 낮다. 서류 1등의 성적을 기준으로 하였으니까.. 문제는 이 기준에서 설정한 사람들 내에서도 문제의 조건으로 탈락하는 사람이 생길 수 있다. 리스트를 2번 순회하였더니 시간초과가 나서 큐를 이용해 최소 힙을 구현하여 수행 시간을 줄였지만 오답처리 되었다.

예를 들어, 서류가 1등이고 면접이 4등인 사람이 있다고 하자. 그리고 A는 서류 2등에 면접2등, B는 서류 3등에 면접 3등이라고 해보자. 나의 로직으로는 두 사람 다 합격할 수 있는 사람이다. 하지만 B는 A보다 서류, 면접 성적이 모두 낮아 합격할 수 없다. 이 방법이 아닌 듯하다.

결과

오답

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

import sys
from heapq import heappop, heappush
t = int(sys.stdin.readline())
for _ in range(t):
    n = int(sys.stdin.readline())
    arr = []
    for _ in range(n):
        heappush(arr,list(map(int,sys.stdin.readline().split())))

    k = arr[0][1]
    cnt = 1
    for i in arr:
        if i[1] < k:
            cnt += 1
    print(cnt)

2차 시도

나의 생각

서류 성적을 index로 하는 배열을 만들고 값으로 면접 성적을 저장했다. 1번 인덱스(서류 성적 1등)부터 순회하며 현재까지 나온 면접 성적의 최솟값을 기준으로 만들었다. 서류 1등은 무조건 합격시키고 기준으로 만든다. 서류 2등부터 순회하며 기존의 만든 기준과 비교한다. 기준보다 높으면 (낮은 등수면) 통과시키고 그 면접 등수를 새로운 기준으로 삼는다. 뒤에 볼 사람들인 방금 본 사람보다 서류 성적이 낮은 사람들이니 이 사람보다 면접 성적이 높아야 하기 때문이다. 면접 성적이 낮은(등수가 높은) 사람은 그냥 무시해도 된다.

결과

정답

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

import sys

t = int(sys.stdin.readline())
for _ in range(t):
    n = int(sys.stdin.readline())
    arr = [0 for _ in range(n+1)]
    for _ in range(n):
        a, b = map(int, sys.stdin.readline().split())
        arr[a] = b
    cnt = 0
    for i in range(1, n+1):
        if i == 1:
            cnt += 1
            limit = arr[i]
        else:
            if arr[i] < limit:
                cnt += 1
                limit = arr[i]
            else:
                continue
    print(cnt)

문제 2 백준 1932

문제 링크

1차 시도

나의 생각

삼각형을 index에 담는다. 줄은 삼각형의 첫번째 index고, 각 줄에서 왼쪽부터 2차원의 index를 가진다. 어떤 줄의 i를 index로 가지는 원소는 이전 줄에서 i를 index로 가지는 원소, i-1을 index로 가지는 원소로 부터 도달할 수 있다. 물론 i와 i-1이 이전 줄에서 존재할 수 있는 index인지는 확인하는 과정이 필요하다. 현재 원소에 도달 가능한 이전 줄의 원소들 중 큰수를 현재 원소에 더해줌으로서 업데이트한다.

결과

정답

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

import sys

n = int(sys.stdin.readline())
arr = []

for i in range(n):
    if i == 0:
        arr.append([int(sys.stdin.readline())])
        continue
    tmp = sys.stdin.readline().rstrip()
    arr.append(list(tmp.split(' ')))
    for x in range(len(arr[-1])):
        arr[-1][x] = int(arr[-1][x])

for i in range(n):
    if not i:
        continue
    j = 0
    while j < len(arr[i]):
        tmp = []
        if j-1 >= 0:
            tmp.append(arr[i-1][j-1])
        if j < len(arr[i-1]):
            tmp.append(arr[i-1][j])
        if tmp:
            arr[i][j] += max(tmp)
        j += 1

print(max(arr[-1]))

문제 3 백준 11727

문제 링크

1차 시도

나의 생각

가로가 n인 직사각형은 가로 길이가 n-2일 떄에 가로 길이가 2인 사각형을 붙인 형태와 가로 길이가 n-1일 때 가로길이가 1인 직사각형 하나를 붙인 형태일 것이다. 가로 길이가 2인 사각형은 가로 두줄이나 세로 두줄 인 경우 2가지이므로 i-2일 때의 2배의 케이스가 생긴다. 가로길이가 1인 직사각형 하나를 붙이는 경우는 앞에 붙이나 뒤에 붙이나 포함되어 있으므로 그대로 case의 갯수만 더해준다.

결과

정답

코드

1
2
3
4
5
6
7
8
9
10
11
12
13

import sys

n = int(sys.stdin.readline())
dp = [0 for _ in range(n+1)]
for i in range(1,n+1):
    if i == 1:
        dp[i] = 1
    elif i == 2:
        dp[i] = 3
    else:
        dp[i] = (dp[i-2]*2 + dp[i-1])%10007
print(dp[n])
CATALOG
    algorithm