파이썬 알고리즘 267번 | [백준 15486번] 퇴사2

Yunny.Log ·2022년 9월 12일

Algorithm

목록 보기

272/318

267. 퇴사2

1) 어떤 전략(알고리즘)으로 해결?

2) 코딩 설명

dp 로 두개를 검사 & 비교해줘야 하는데
- 바로 상담을 하는 경우와
- 상담을 하지 않는 경우
  일케 두가지..

<내 풀이>


import sys

n = int(sys.stdin.readline())
tpsave=[]
tpsave.append((0,0)) # 인덱스 0 인 자리 단순 채움용
dp = [0 for _ in range(n+2)]

for j in range(n) :
    t,p = map(int, sys.stdin.readline().split())
    # 걸리는 상담 시간, 보상 가격 순으로 저장 
    tpsave.append((t,p))

# 1일차부터 n일차까지 돌아줄 것임 
for i in range(1,n+1) :
    # (1) 만약 상담하기로 선택하면 비교해주기
    target = i+tpsave[i][0]
    if target<=n+1 :  # n+1도 포함시켜줘야 한다 ..
        # 왜냐면 주어진 n=7이고 그때 소요 시간이 1일이면 상담 가능임
        # 7일 하루를 쓰는 거니깐,
        # 그리고 이는 8일에 기록돼야 하므로 target 은 n+1까지 가능
        dp[target] = max(dp[target], tpsave[i][1]+dp[i])

    # (2) 선택 안하는 경우 (while 문을 안써도 되는 이유)
    dp[i+1] = max(dp[i+1], dp[i]) 

# n+1 일째 되는 날 퇴사하니깐 n+1일 째의 보상을 출력
print(dp[n+1])

< 내 틀렸던 풀이, 문제점>

메모리초과

from collections import deque
import sys

money = -1
n = int(sys.stdin.readline())
dict={}

for j in range(n) :
    t,p = map(int, sys.stdin.readline().split())
    dict[j+1]=[]
    dict[j+1].append(t)
    dict[j+1].append(p)

q=deque()

for i in range(1,n+1) :
    if i+dict[i][0]<=n : 
        q.append((i,dict[i][1]))

while q :
    nowday, nowprice = q.popleft()
    if money<nowprice:
        money=nowprice

    cand = []
    for c in range(nowday+dict[nowday][0],n+1):
        if c+dict[c][0]-1>=n+1:
            break
        cand.append(c)

    for ca in cand : 
            q.append((ca, nowprice+dict[ca][1]))

print(money)

근데 문제 유형 봤더니 dp 임
dp 는 브루트포스 방식으로 다 살펴보는 방식으로 봤을 때 뭔가 초과, 에바 상태이면 생각해내야 하는 기법이지.

memory exceeded


from collections import deque
import sys

n = int(sys.stdin.readline())
dict={}
dp = [0 for _ in range(n+1)]
for j in range(n) :
    t,p = map(int, sys.stdin.readline().split())
    dict[j+1]=[]
    dict[j+1].append(t)
    dict[j+1].append(p)
    if(j+1+dict[j+1][0]-1<n+1) : 
        dp[j+1] = p

q=deque()

for i in range(1,n+1) :
    if i+dict[i][0]<=n : 
        q.append((i,dict[i][1]))

while q :
    nowday, nowprice = q.popleft()
    for c in range(nowday+dict[nowday][0],n+1):
        if c+dict[c][0]-1>=n+1:
            break
        dp[c] = max(dp[c], nowprice+dict[c][1])
        q.append((c, nowprice+dict[c][1]))
print(max(dp))

dp 로 바꾼다

하핫 메모리초과는 안 나는데 시간초과 남

from collections import deque
import sys

n = int(sys.stdin.readline())
dict=[]
dict.append((-1,-1))

dp = [0 for _ in range(n+1)]
for j in range(n) :
    t,p = map(int, sys.stdin.readline().split())
    dict.append((t,p))
    if(j+1+dict[j+1][0]-1<n+1) : 
        dp[j+1] = p

for i in range(1,n+1) :
    if i+dict[i][0]<=n : 
        nowday, nowprice = i,dp[i]
        for c in range(nowday+dict[nowday][0],n+1):
            if c+dict[c][0]-1>=n+1:
                break
            dp[c] = max(dp[c], nowprice+dict[c][1])

print(max(dp))

시간초과의 늪,,

import sys

n = int(sys.stdin.readline())
dict=[]
dict.append((-1,-1))
endpoint = n+1
dp = [0 for _ in range(n+1)]

for j in range(n) :
    t,p = map(int, sys.stdin.readline().split())
    dict.append((t,p))
    if(j+1+dict[j+1][0]-1<n+1) : 
        dp[j+1] = p
    else : 
        if endpoint==n+1 : 
            endpoint = j+1

for i in range(1,endpoint) :
    #print(dp)
    target = i+dict[i][0]
    while target<=n and target<endpoint:
        dp[target] = max(dp[target], dict[target][1]+dp[i])
        target+=1

print(max(dp))

오류 투성이

import sys

n = int(sys.stdin.readline())
dict=[]
dict.append((-1,-1))
endpoint = n+1
dp = [0 for _ in range(n+1)]

for j in range(n) :
    t,p = map(int, sys.stdin.readline().split())
    dict.append((t,p))
    if(j+1+dict[j+1][0]-1<n+1) : 
        dp[j+1] = p
    else : 
        if endpoint==n+1 : 
            endpoint = j+1

for i in range(1,endpoint) :

    target = i+dict[i][0]
    if target<endpoint:
        dp[target] = max(dp[target], dict[target][1]+dp[i])
    if i+1<endpoint:
        dp[i+1] = max(dp[i+1], dp[i])
print(dp)
print(max(dp))