오늘은 깃허브 pages로 블로그를 만들었다. 만들고나니 너무 졸리지만 5개는 풀자!

1149번 RGB거리

N개의 집을 빨,초,파 로 색칠하는 최소 비용 구하기 어제 새벽에 2시간 봤는데 dfs의 백트래킹으로 푸니 시간초과가 났다ㅠ_ㅠ 나름 이쁘게 풀었다고 생각했는데… N이 최대 1000이고 시간 제한이 0.5초이므로 선형적으로 풀어야하는데 그럼 dp 뿐이다. dp로 풀려고 했는데 잘 되지 않아 결국 검색 찬스… 아이디어를 얻고 오늘 다시 푸니 10분만에 풀렸다… 당연한거겠지만ㅋㅋ

import sys

n = int(input())
cost = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
dp = [[0 for _ in range(3)] for _ in range(n)]
dp[0] = cost[0]

for i in range(1, n):
    dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + cost[i][0]
    dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + cost[i][1]
    dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + cost[i][2]

print(min(dp[n-1]))

멋진 코드 발견…

import sys
snput = lambda: sys.stdin.readline().rstrip()

cnt = int(snput())
c_L = list(map(int, snput().split()))
for _ in range(cnt - 1):
    n_L = list(map(int, snput().split()))
    for i in range(3):
        n_L[i] += min(c_L[(i + 1) % 3], c_L[(i + 2) % 3])
    c_L = n_L

print(min(c_L))

회의실에 최대 회의 배정하기

4시간 걸렸나?… 2시간 동안 못풀었다. 백트래킹으로 풀려고 처음 시도 했으나 시간 초과가 너무 당연해보였다. 10^5… 10^3 정도면 백트래킹으로 풀렸을것같다. dp 밖에 없는데 그러려면 정렬이 돼야한다. 무엇을 기준으로 정렬할지 한참 고민했다. 그리고 정렬해서 풀었는데 그럼 시간 초과가 났다. 당연하다 이중포문으로 풀었는데 break할 수가 없기 때문에 마지막에 10^5 x 10^5의 경우가 생긴다. 이것 저것 해보다 각 회의의 소요시간을 구해서 (시작시간, 소요시간) 을 저장한 뒤 소요시간이 적은 걸 고르면 최대 회의가 가능하지 않을까? 생각해서 소요시간으로 무언갈 해보려고 했는데 잘 되지 않았다. 그 이유는 시작 시간과 끝나는 시간이 최대 2^31-1 이기 때문이다. 24(하루의 시간)이었으면 이렇게 풀 수 있었을테다. 자다가 악몽처럼 이 문제 때문에 깼다ㅋㅋ 자면서 꿈에서도 풀고 있었던 느낌?;; 그래서 눈 감고 또 막 이것저것 바둑처럼 착수하듯이 여러 경우를 생각해보다가 이거다 하고 잠이 팍 깨서 풀어나갔다. 거기다 결정적으로 힌트로 주어진 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. 요거 때문에 풀 수 있었다.(정렬 순서를 여기서 힌트를 얻음)

3,5를 탐색할때 그 앞에서 end 시작이 3보다 작은게 있는지 확인 필요 이전 dp[i-1] 에는 1,4가 들어가 있고 지금의 end보다 이전의 end가 더 작으므로 1,4를 그대로 남겨둔다 dp[i] 는 여전히 1,4 이고 cnt 는 그대로 1이다. 3,8도 마찬가지 로직 5,7을 만났다 dp[i-1]에 있는 end인 4보다 start가 크다. 무조건 채택이다. end 비교는 필요없다. dp[i]로 5,7을 채택하며 cnt를 증가시켜 2로 만든다 5,9는 또 end 와의 비교로 무시된다. 6,10을 만났다. 5,7의 end보다 더 작다. 그리고 10 7보다 크기 때문에 패스한다 8, 11을 채택.

힌트의 순서대로 정렬해놓고 어떻게 할지 그려본 글이다. 이 글 그대로 구현한 코드가 밑이다.

import sys

n = int(input())
meeting = []

for _ in range(n):
    start, end = (map(int, sys.stdin.readline().split()))
    meeting.append([start, end])

meeting.sort(key = lambda x : (x[0], x[1]))

dp = [[0,0] for _ in range(n)]
dp[0] = meeting[0]
cnt = 1
start = 0
end = 1

for i in range(1, n):
    # i번째 회의의 시작시간이 최적화된 마지막 회의의 종료시간보다 빠르다는 것은
    # 이번 차례에 cnt를 증가 시킬 수 없다는 뜻이며
    # 잘해봐야 dp[i-1]를 대체하는 것 밖에 안된다. 
    # 그마저도 안되면 그냥 무시한다.  
    if meeting[i][start] < dp[i-1][end]:
        if meeting[i][end] < dp[i-1][end]:
            dp[i] = meeting[i]
        else:
            dp[i] = dp[i-1]
    # 반대의 경우라면 무조건 cnt + 1을 이루어낼 수 있다.
    # 또한 최적화된 dp[i]로 바로 채택한다.
    else:
        dp[i] = meeting[i]
        cnt += 1

print(cnt)

블로그 글을 쓰기 시작했더니 주석에 감성이 담긴다. 새벽에 풀어서 그런가?ㅋㅋㅋ c에 1 더하라는 소리를 뭐 저렇게 썼지? 오글거려 ㅋ 그리고 이거 풀면서도 느꼈지만 dp가 필요없고 그냥 마지막회의 lastMeeting 튜플 하나만 있어도 된다. 다른 사람들 보니 그렇게 구현한 코드가 더 많다.