Enochkon's blog

문제

코드

import sys
import copy
input = sys.stdin.readline
n= int(input())
# dp배열을 쓰고 싶지만 메모리가 부족하여 현재층과 바로 위층에 사용한 배열만 초기화
bq=[[0,0],[0,0],[0,0]]
cq=[[0,0],[0,0],[0,0]]
for i in range(n):
    arr=list(map(int,input().split()))
    #최대값 구하기
    cq[0][0]=max(bq[0][0],bq[1][0])+arr[0]
    cq[1][0]=max(bq[0][0],bq[1][0],bq[2][0])+arr[1]
    cq[2][0]=max(bq[1][0],bq[2][0])+arr[2]

		#최소값 구하기
    cq[0][1]=min(bq[0][1],bq[1][1])+arr[0]
    cq[1][1]=min(bq[0][1],bq[1][1],bq[2][1])+arr[1]
    cq[2][1]=min(bq[1][1],bq[2][1])+arr[2]
    bq=copy.deepcopy(cq)
resMax=0
resMin=100000000
for i in range(3):
    resMax=max(resMax,max(bq[i]))
    resMin=min(resMin,min(bq[i]))
print(resMax,resMin)

풀이

• 간단한(하지만 조건있는) dp 문제
• 메모리가 굉장히 작으므로, 전체를 저장하는게 아닌 사용하는 부분을 계속 업데이트 하는 방식으로 푼다.

1. 높이 n을 입력받는다.
   • dp 문제이지만 여기서 메모리 크기가 4mb이다. 그러므로 층을 한층씩 내려가면서 본다.
   • 각 층에서 내려갈 수 있는 부분은 인접해 있는 부분이기 때문에 거꾸로 밑층에서도 인접한 곳에서만 올 수 있다.
   • 그러므로 dp[i][0] (왼쪽) : dp[i-1][0] (왼쪽 위), dp[i-1][1] (가운데 위) 중 하나 dp[i][1] (가운데쪽) : dp[i-1][0] (왼쪽 위), dp[i-1][1] (가운데 위), dp[i-1][2] (오른쪽 위) 중 하나 dp[i][2] (오른쪽) : dp[i-1][1] (가운데 위), dp[i-1][2] (오른쪽 위) 중 하나 이다.
   • 최소값과 최대값을 둘다 구하므로, 각각의 위치에 최소,최대를 둘다 구해서 표시해준다.
   • 현재 층(cq)과 바로 위층(bq)만을 사용하고, 다음 층으로 넘어가면 bq=cq로 업데이트 해준다.n만큼 한층씩 내려가면서 최대값과 최솟값을 기록하면서 내려간다.

2. 반복문을 전부 돌고, 1층에서의 최대값과 최소값을 찾아서 출력한다.

특이사항

• dp의 점화식은 대놓고 문제에서 그림으로 주지만, 메모리가 굉장히 제한적이여서 쉽지 않은 문제였다.
• dp배열을 cq와 bq로 바꿨는데도 메모리 초과→ 입력받는 arr도 한줄씩 받게 변경 → 시간초과가 나서 sys로 입력속도 빠르게함 → 성공

문제

코드

T = int(input())
for _ in range(T):
    N = int(input())
    arr = [list(map(int,input().split()))]
    arr.append(list(map(int,input().split())))
    res=[[0 for _ in range(N+1)] for _ in range(2)]
    for i in range(N):
        if(i==0):
            res[0][i+1]=arr[0][i]
            res[1][i+1]=arr[1][i]
            continue
        res[0][i+1]=max(res[1][i]+arr[0][i],res[1][i-1]+arr[0][i])
        res[1][i+1]=max(res[0][i]+arr[1][i],res[0][i-1]+arr[1][i])
    print(max(max(res[0]),max(res[1])))

풀이

1. 시행횟수 T와 스티커사진의 길이 N, 그리고 각 스티커의 점수를 입력 받는다.
2. 입력 받은 스티커 사진을 조건에 맞게 찢어서 최대 점수를 얻는 방법을 구한다. (res배열은 해당 위치 최고 점수의 합)1 2

   1	2
   		3

   1. 우선 첫번째 위치의 경우에는 온전히 res배열에 그 스티커의 점수를 저장한다.
   2. 두번째부터 점화식을 세워서 구해준다.
   3. 위의 표처럼 이런 상황에서 3의 최대값을 구하려면 우선 (2까지의 점수합 + 3의 점수)이 있다. 그리고 또한 스티커를 뗀 부분의 상하좌우를 못쓰게 되므로 만약 1까지의 점수합이 더 크다면 (1까지의 점수합 + 3의 점수) 의 경우가 존재한다. 즉 max((2까지의 점수합 + 3의 점수), (1까지의 점수합 + 3의 점수))을 구하게 된다면 해당 위치의 스티커의 최대점수를 얻을 수 있다.
   4. 끝까지 최대점수를 구한뒤 max()함수를 사용하여 최대값을 구한 후 출력해준다.

문제

1535번: 안녕

코드

n = int(input())
lost = list(map(int,input().split()))
happy = list(map(int,input().split()))
hp = 100
pleasure = 0
arr= [[0 for _ in range(101)] for _ in range(n+1)]

for i in range(1,n+1):
    for j in range(1,101):
        if(j-lost[i-1]>0):
            arr[i][j] = max(arr[i-1][j], arr[i-1][j-lost[i-1]] + happy[i-1])
        else:
            arr[i][j]=arr[i-1][j]

print(arr[n][100])

풀이

• 간단한 dp 문제

1. 사용 체력과 얻는 기쁨을 배열로 받아준다.
2. dp 배열을 arr[i][j] (i : 체력, j : 사람 순서)로 작성해준다.
3. 이중 반복문을 사용해서 체력이 0 이하가 되면 바로 인사를 하지 않고 바로 전 사람까지의 기쁨 값을 가져온다 (i-1)
   1. 체력이 0이하로 떨어지지 않으면 바로전까지의 기쁨 값과, 인사를 했을 때 추가되는 값중 큰 값을 새로 입력해준다.
4. 전부 순회한 후 제일 마지막 최대값을 출력해준다.