일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
- 브루트포스
- 애드 혹
- 수학
- BFS
- 그래프
- 트리
- 구현
- 슬라이딩 윈도우
- 13164
- boj
- 모던 JavaScript 튜토리얼
- 에라토스테네스의 체
- DP
- SSAFY
- 그리디
- 싸피
- 맵
- 세그먼트 트리
- DFS
- 해시 테이블
- 문자열
- 정수론
- 2357
- 투 포인터
- 이분 탐색
- Python
- JavaScript
- 정렬
- 플로이드-워셜
- 누적 합
- Today
- Total
흙금이네 블로그
[BOJ] 2169 - 로봇 조종하기 (Python) 본문
아이디어
위쪽, 왼쪽, 오른쪽의 가능한 지역 중 최대 가치를 더해 나간다.
풀이
입력 받은 N, M을 저장하고, 첫 행을 입력 받아 리스트 dp에 저장한다.
첫 행의 지역들은 시작 지점을 제외하고는 왼쪽 지역을 탐사해야 이동할 수 있으므로, dp를 오른쪽으로 누적하여 더한다.
첫 행과 마지막 행의 지역들을 제외한 지역들을 처리하기 위해 N-2의 크기로 for문을 실행한다(N > 2일 때 실행).
우선 현재 행을 arr에 입력 받고, arr과 같은 크기로 0이 채워진 리스트 temp를 생성한다.
temp에는 왼쪽에서 오른쪽으로 탐사해 나갈 때의 최대 가치를 저장한다.
temp의 첫 번째 값은 arr의 첫 번째 값(현재 지역 가치)과 dp의 첫 번째 값(위쪽 지역 최대 누적 가치)의 합으로 저장하고,
나머지 값들은 왼쪽 지역(temp)과 위쪽 지역(dp)의 최대 누적 가치 중 더 큰 값과 현재 지역 가치(arr)를 더해 나간다.
이번에는 오른쪽에서 왼쪽으로 탐사해 나갈 때의 최대 가치를 arr에 저장한다.
arr의 마지막 값에 dp의 마지막 값(위쪽 지역 최대 누적 가치)를 더하고,
나머지 값들은 오른쪽 지역(arr)과 위쪽 지역(dp)의 최대 누적 가치 중 더 큰 값을 더해 나간다.
마지막으로 temp와 arr의 값들을 서로 비교해 더 큰 값을 arr에 저장하고 dp에 arr을 할당한다.
N이 1일 때는 첫 for문에서 구한 dp의 마지막 값이 결과값이 되므로 마지막 행은 N > 1일 때 계산한다.
마지막 행은 왼쪽 방향으로 탐사가 불가능하므로 오른쪽 방향으로 최대 누적 가치를 더해 나가고, 결과값을 출력한다.
import sys
input = sys.stdin.readline
def solution():
N, M = map(int, input().split())
dp = list(map(int, input().split()))
for i in range(M-1):
dp[i+1] += dp[i]
for _ in range(N-2):
arr = list(map(int, input().split()))
temp = [0]*M
temp[0] = arr[0]+dp[0]
for i in range(1, M):
temp[i] = arr[i]+max(dp[i], temp[i-1])
arr[-1] += dp[-1]
for i in range(M-2, -1, -1):
arr[i] += max(dp[i], arr[i+1])
for i in range(M):
arr[i] = max(arr[i], temp[i])
dp = arr
if N > 1:
arr = list(map(int, input().split()))
arr[0] += dp[0]
for i in range(1, M):
arr[i] += max(dp[i], arr[i-1])
dp = arr
print(dp[-1])
solution()
한 행씩 입력 받아 처리할 수 있으므로 한번에 모든 행을 입력 받아 저장하지 않아도 된다.
# 메모리가 더 많이 사용되는 코드
N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
함수를 사용하지 않은 코드보다 함수를 정의하여 함수 내부에서 동작하도록 한 코드가 더 빨랐다.
# 1.
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
dp = list(map(int, input().split()))
...
# 2. 더 빠른 코드
import sys
input = sys.stdin.readline
def solution():
N, M = map(int, input().split())
dp = list(map(int, input().split()))
...
'알고리즘' 카테고리의 다른 글
[BOJ] 2616 - 소형기관차 (Python) (0) | 2023.01.27 |
---|---|
[BOJ] 20437 - 문자열 게임 2 (Python, JavaScript) (0) | 2023.01.27 |
[BOJ] 19583 - 싸이버개강총회 (Python, JavaScript) (0) | 2023.01.25 |
[BOJ] 1937 - 욕심쟁이 판다 (Python) (0) | 2023.01.25 |
[BOJ] 6550 - 부분 문자열 (Python, JavaScript) (0) | 2023.01.25 |