Enochkon's blog

문제

코드

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. 전부 순회한 후 제일 마지막 최대값을 출력해준다.