퇴사


일주일 전에 푼 문제였다. 이번에는 빠른 날짜부터 dfs로 탐색해 나가는 것이 아니라, 뒤 부터 이 날의 일을 반드시 한다면(퇴사전에 끝낼 수 있는 경우) 최대 얼마의 금액을 받을 수 있는지 DP로 저장해나가며 풀었다.

CODE

import sys
read=sys.stdin.readline

n=int(read())
work=list(list(map(int,read().split())) for _ in range(n))

dp=list(0 for _ in range(n))

for i in range(n-1,-1,-1):
    if work[i][0]+i<=n:
        dp[i]=work[i][1]
        if work[i][0]+i<n:
            dp[i]+=max(dp[work[i][0]+i:])

print(max(dp))



경쟁적 전염


바이러스가 종류별로 여러군데에 있는 경우를 생각하지 못해 조금 헤맸다. 예를 들어서 1,2,2,3 이렇게 있는 경우 2가 두번 카운팅 되어 압도적으로 빨리 번식하게 되는 결과를 가져왔다.

그래서 집합을 활용해 중복을 없애 해결해주었다.

CODE

import sys
read=sys.stdin.readline

n,k=map(int,read().split())
virus=list(list(map(int,read().split())) for _ in range(n))
s,x,y=map(int,read().split())

save=dict()
type_virus=[]
for i in range(n):
    for j in range(n):
        X=virus[i][j]
        if X!=0:
            if X in save: save[X]+=[[i,j]]
            else: save[X]=[[i,j]]
            type_virus.append(X)
type_virus=list(set(type_virus))
type_virus.sort()
da=[0,1,0,-1]
db=[1,0,-1,0]

def dfs():
    if all(0 not in v for v in virus): return
    for v in type_virus:
        tmp=[]
        for i,j in save[v]:
            for a,b in zip(da,db):
                ia=i+a
                jb=j+b
                if 0<=ia<n and 0<=jb<n and virus[ia][jb]==0:
                    virus[ia][jb]=v
                    tmp.append([ia,jb])
        save[v]=tmp

for _ in range(s):
    dfs()

print(virus[x-1][y-1])