태야

<내 코드>

N = int(input())
H = list(map(int, input().split()))
result = [0] * N

for i in range(N):
    cnt_zero = 0

    for j in range(N):
        if cnt_zero == H[i] and result[j] == 0:
            result[j] = i + 1  # 수 1 ~ N
            break
        elif(result[j] == 0):
            cnt_zero += 1

print(*result)

입력 값으로 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. 그리고 줄을 선 순서대로 키를 출력하면 된다. 

# result
# 입력: [2, 1, 1, 0]
[0, 0, 1, 0]
[0, 2, 1, 0]
[0, 2, 1, 3]
[4, 2, 1, 3]

차례대로 각자 왼쪽에 큰 사람이 몇 명인지를 0의 개수로 판단해서 자리에 넣어준다. 예를 들어 왼쪽에 2명이 있다 하면 결과값 배열에 [0, 0, 현재,...] 즉, 자신보다 큰 2명의 자리를 비워두고 자리에 들어가면 된다. 그렇게 되면 다음 사람은 앞전보다 큰 사람이기 때문에 앞사람 위치는 무시하고 자신보다 큰 사람 수와 0의 수만 같으면 그 자리에 들어가면 된다.

<내 코드>

T = int(input())

A, B, C = 0, 0, 0

while T > 0:
    if T >= 300:
        A = (T // 300)
        T = (T % 300)
    if (T >= 60) and (T < 300):
        B = (T // 60)
        T = (T % 60)
    if (T < 60):
        C = (T // 10)
        if (T % 10) == 0:
            print("{} {} {}".format(A, B, C))
            break
        else:
            print(-1)
            break

특별히 어려운 조건이 없는 문제였다. 최소한의 버튼 클릭 수를 구하기 위해 입력값을 큰 값으로 최대한 나누면 된다. 입력 값이 단위별로 나눌 수 있는 값인지 판단 후 계산을 하고 몫을 출력해주면 된다. 마지막에 10초로 나눴을 때 나머지가 0이 아니면 -1을 출력한다.

<내 코드>

def recruit(num, score):
    min_interview = score[0][1] # 첫번째 지원자 면접 등수
    cnt = 1 # 첫 번째 지원자는 서류점수가 1등이기에 무조건 뽑힘
    for i in range(1, num):  # 1번 ~ n-1번

        if score[i][1] < min_interview:  # 뽑히는 경우
            min_interview = score[i][1] # 더 높은 등수로 변경
            cnt += 1

    return cnt


tests = int(input())

for _ in range(tests):
    num = int(input())
    score = [list(map(int, input().split())) for _ in range(num)]
    score.sort(key=lambda x: x[0])  # 서류 시험 등수 오름차순
    print(recruit(num, score))

Python3로 제출하면 시간 초과가 나고, pypy로 제출하니 통과가 됐다. for문을 최대로 줄이려고 해 봤지만 다른 방법을 찾기가 쉽지 않았다.

문제 조건

- 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발.

- 즉, 현재 지원자의 서류 성적보다  더 높은 서류 성적을 가진 사람들보다 면접 성적이 높아야 선발된다.

따라서 우선 성적을 '서류 성적순'으로 정렬시킨다. 그리고 가장 높은 서류 성적을 가진 사람은 면접이 낮더라도 무조건 선발된다. 그래서 첫 번째 지원자의 면접 성적을 min_interview에 담고 그 값을 다음 사람들과 비교해나간다. 

더 낮은(즉, 더 좋은 면접 성적) 성적을 가진 사람이 있으면 min_interview에 담는다. 그렇게 되면 특정 지원자의 면접시험 성적과 min_interview만 비교해 특정 지원자의 선발 여부를 결정할 수 있게 된다. 왜냐하면 이미 서류 성적순으로 정렬이 됐기에 지나온 지원자들보다 면접 성적만 낮지 않으면 되기 때문이다.

<내 코드>

sugar = int(input())
result = 0
while sugar != 0:
    if sugar < 0:
        result = -1
        break

    if (sugar % 5) == 0:
        result += (sugar // 5)
        sugar = 0
    else:
        sugar -= 3
        result += 1

print(result)

일단 설탕의 무게가 큰 단위인 5로 나눠지면 몫을 result에 담고 설탕 무게를 0으로 만든다. 만약 5로 나눠지지 않는다면 설탕에서 -3을 해주고 result를 1증가시킨다. 그러다 설탕이 0보다 작아지는 경우에는 5, 3으로 나눌 수 없는 값이기 때문에 -1을 출력하고 반복문을 종료한다.

<내 코드>

N = int(input())

times = [list(map(int, input().split())) for _ in range(N)]
times.sort(key=lambda x: (x[1], x[0])) # 끝 시간으로 정렬 후, 시작 시간으로 정렬

cnt = 1
end_time = times[0][1]
for i in range(1, N):
    if times[i][0] >= end_time: # 앞 요소의 끝 시간보다 현재 요소의 시작시간이 크거나 같을 때
        cnt += 1
        end_time = times[i][1]

print(cnt)

문제에서 제약조건이 다음과 같이 주어졌다.

- 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.

- 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

최대한 많은 회의를 잡기 위해서는 끝나는 시간이 짧아야 한다. 회의가 빨리 끝나야 다음 회의를 시작할 수 있다. 

그래서 우선 끝나는 시간으로 정렬한다. 여기서 중요한 것이 시작 시간과 끝나는 시간이 같은 케이스다.

예를 들어 (2,2) 와 (1,2) 있을 때 끝나는 시간으로 정렬을 한다면 (2,2)가 먼저 정렬되고 (1,2)가 무시된다. 그래서 시작과 끝 시간이 같은 경우는 시작 시간 기준으로 다시 정렬을 해줘야 한다.

<내 코드>

n = input().split('-')
result = 0

for i in n[0].split('+'):
    result += int(i)

for j in n[1:]:
    for k in j.split('+'):
        result -= int(k)

print(result)

적절한 괄호를 쳐서 최솟값을 만드는 문제다. 최솟값을 만들려면 -의 값이 커야 하기에 - 사이에 +로 연결된 값들을 다 더한 후 마지막 빼주면 최솟값을 만들 수 있다. 어떤 점에서 그리디 문제인지는 감이 오지 않는 문제다...

<내 코드>

n = int(input())
tri = [list(map(int, input().split())) for _ in range(n)]
k = 2
for i in range(1, n):
    for j in range(len(tri[i])):
        if j == 0:  # 가장 왼쪽값일 경우 현재 값이랑 바로 위랑 더함
            tri[i][j] = tri[i-1][j] + tri[i][j]
        elif j == len(tri[i])-1:    # 가장 오른쪽일 경우 현재 값이랑 바로 위랑 더함
            tri[i][j] = tri[i-1][-1] + tri[i][j]
        else:  # 양 끝값이 아닌, 중간일 경우, 대각선 왼쪽과 오른쪽 중 큰 값과 더함
            tri[i][j] = max(tri[i-1][j-1], tri[i-1][j]) + tri[i][j]
    k += 1
print(max(tri[n-1]))

규칙을 찾아서 재귀 형태의 점화식을 찾아내는 것이 중요했다. 삼각형의 가장 왼쪽과 오른쪽 값은 위의 값과 바로 더해주면 되고, 중간의 값들은 대각선 왼쪽과 오른쪽의 값 중 최댓값과 더해줬다. 

<내 코드>

n = int(input())
memo = [0 for _ in range(101)]

for i in range(0, 4):
    memo[i] = 1
for j in range(4, 6):
    memo[j] = 2

for _ in range(n):
    m = int(input())
    for k in range(6, m+1):  # 6 ~ m-1
        memo[k] = memo[k-1] + memo[k-5]

    print(memo[m])

피보나치 수열과 비슷한 맥락으로 규칙을 찾아 점화식을 세우면 간단하게 풀 수 있었다.

인덱스 0번 ~ 4번까지는 1과 2로 넣어주고 그 다음부터는 점화식을 통해 값을 구해나가는 구조였다. 인덱스 값을 0번째 부터 설정해서 뒤에서 조금 헷갈린거 말고는 크게 어렵지 않았다.