[백준] 9465번 스티커
9706 단어 백준파이썬알고리즘다이나믹 프로그래밍다이나믹 프로그래밍
문제 링크
문제 설명
- 2행 N열 보드가 주어진다
- 스티커마다 점수가 주어진다
- 한 스티커를 선택하면 인접한 스티커는 선택할 수 없다
- 점수의 최댓값 출력
풀이
- dp[0][0], dp[1][0], dp[0][1], ... 순서로 돌면서 점수 계산
- 어차피 위, 아래는 동시에 선택할 수 없기 때문에 나누어 생각한다
- 해당 좌표까지의 최댓값 저장
- 위쪽일 때
- 해당 좌표를 선택할 경우
- 왼쪽, 아래쪽은 선택할 수 없기 때문에 (왼쪽아래 까지의 최댓값) + (현재 스티커 점수)
- 해당 좌표를 선택하지 않을 경우
- max(왼쪽까지의 최댓값, 왼쪽아래까지의 최댓값)
- 아래쪽일 때
- 해당 좌표를 선택할 경우
- (왼쪽위까지의 최댓값) + (현재 스티커 점수)
- 해당 좌표를 선택하지 않을 경우
- max(왼쪽위까지의 최댓값, 왼쪽까지의 최댓값)
느낀 점
- 처음에 문제가 잘 이해가 안됐다
- 사용한다는게 무엇인지..
- 그냥 선택한다고 이해했다
- DP를 이용해야겠다고 생각은 들었는데 어떻게 구현해야 하는지 조금 고민이 됐다
- 반복문 순서를 행이 아닌 열을 우선으로 진행해야겠다고 생각했다
코드
import sys
def init():
n = int(ipt())
board = [list(map(int, ipt().split())) for _ in range(2)]
dp = [[0] * n for _ in range(2)]
dp[0][0] = board[0][0]
dp[1][0] = board[1][0]
return n, board, dp
ipt = sys.stdin.readline
tc = int(ipt())
for _ in range(tc):
n, board, dp = init()
for x in range(1, n):
for y in range(2):
if y % 2 == 0:
dp[y][x] = max(
board[y][x] + dp[y+1][x-1],
max(dp[y][x-1], dp[y+1][x-1])
)
else:
dp[y][x] = max(
board[y][x] + dp[y-1][x-1],
max(dp[y-1][x-1], dp[y][x-1])
)
print(max(map(max, dp)))
Author And Source
이 문제에 관하여([백준] 9465번 스티커), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@leehj8896/백준-9465번-스티커
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
- 2행 N열 보드가 주어진다
- 스티커마다 점수가 주어진다
- 한 스티커를 선택하면 인접한 스티커는 선택할 수 없다
- 점수의 최댓값 출력
풀이
- dp[0][0], dp[1][0], dp[0][1], ... 순서로 돌면서 점수 계산
- 어차피 위, 아래는 동시에 선택할 수 없기 때문에 나누어 생각한다
- 해당 좌표까지의 최댓값 저장
- 위쪽일 때
- 해당 좌표를 선택할 경우
- 왼쪽, 아래쪽은 선택할 수 없기 때문에 (왼쪽아래 까지의 최댓값) + (현재 스티커 점수)
- 해당 좌표를 선택하지 않을 경우
- max(왼쪽까지의 최댓값, 왼쪽아래까지의 최댓값)
- 아래쪽일 때
- 해당 좌표를 선택할 경우
- (왼쪽위까지의 최댓값) + (현재 스티커 점수)
- 해당 좌표를 선택하지 않을 경우
- max(왼쪽위까지의 최댓값, 왼쪽까지의 최댓값)
느낀 점
- 처음에 문제가 잘 이해가 안됐다
- 사용한다는게 무엇인지..
- 그냥 선택한다고 이해했다
- DP를 이용해야겠다고 생각은 들었는데 어떻게 구현해야 하는지 조금 고민이 됐다
- 반복문 순서를 행이 아닌 열을 우선으로 진행해야겠다고 생각했다
코드
import sys
def init():
n = int(ipt())
board = [list(map(int, ipt().split())) for _ in range(2)]
dp = [[0] * n for _ in range(2)]
dp[0][0] = board[0][0]
dp[1][0] = board[1][0]
return n, board, dp
ipt = sys.stdin.readline
tc = int(ipt())
for _ in range(tc):
n, board, dp = init()
for x in range(1, n):
for y in range(2):
if y % 2 == 0:
dp[y][x] = max(
board[y][x] + dp[y+1][x-1],
max(dp[y][x-1], dp[y+1][x-1])
)
else:
dp[y][x] = max(
board[y][x] + dp[y-1][x-1],
max(dp[y-1][x-1], dp[y][x-1])
)
print(max(map(max, dp)))
Author And Source
이 문제에 관하여([백준] 9465번 스티커), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@leehj8896/백준-9465번-스티커
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
- 해당 좌표를 선택할 경우
- 왼쪽, 아래쪽은 선택할 수 없기 때문에 (왼쪽아래 까지의 최댓값) + (현재 스티커 점수)
- 해당 좌표를 선택하지 않을 경우
- max(왼쪽까지의 최댓값, 왼쪽아래까지의 최댓값)
- 해당 좌표를 선택할 경우
- (왼쪽위까지의 최댓값) + (현재 스티커 점수)
- 해당 좌표를 선택하지 않을 경우
- max(왼쪽위까지의 최댓값, 왼쪽까지의 최댓값)
- 처음에 문제가 잘 이해가 안됐다
- 사용한다는게 무엇인지..
- 그냥 선택한다고 이해했다
- DP를 이용해야겠다고 생각은 들었는데 어떻게 구현해야 하는지 조금 고민이 됐다
- 반복문 순서를 행이 아닌 열을 우선으로 진행해야겠다고 생각했다
코드
import sys
def init():
n = int(ipt())
board = [list(map(int, ipt().split())) for _ in range(2)]
dp = [[0] * n for _ in range(2)]
dp[0][0] = board[0][0]
dp[1][0] = board[1][0]
return n, board, dp
ipt = sys.stdin.readline
tc = int(ipt())
for _ in range(tc):
n, board, dp = init()
for x in range(1, n):
for y in range(2):
if y % 2 == 0:
dp[y][x] = max(
board[y][x] + dp[y+1][x-1],
max(dp[y][x-1], dp[y+1][x-1])
)
else:
dp[y][x] = max(
board[y][x] + dp[y-1][x-1],
max(dp[y-1][x-1], dp[y][x-1])
)
print(max(map(max, dp)))
Author And Source
이 문제에 관하여([백준] 9465번 스티커), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@leehj8896/백준-9465번-스티커
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
import sys
def init():
n = int(ipt())
board = [list(map(int, ipt().split())) for _ in range(2)]
dp = [[0] * n for _ in range(2)]
dp[0][0] = board[0][0]
dp[1][0] = board[1][0]
return n, board, dp
ipt = sys.stdin.readline
tc = int(ipt())
for _ in range(tc):
n, board, dp = init()
for x in range(1, n):
for y in range(2):
if y % 2 == 0:
dp[y][x] = max(
board[y][x] + dp[y+1][x-1],
max(dp[y][x-1], dp[y+1][x-1])
)
else:
dp[y][x] = max(
board[y][x] + dp[y-1][x-1],
max(dp[y-1][x-1], dp[y][x-1])
)
print(max(map(max, dp)))
Author And Source
이 문제에 관하여([백준] 9465번 스티커), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@leehj8896/백준-9465번-스티커저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)