https://www.acmicpc.net/problem/14430
WOOK은 언제나 제한된 범위 내에서 자원을 탐색하며, 왼쪽 위 (1,1)부터 오른쪽 아래 (N,M)까지 자원을 탐색한다. WOOK은 한 번에 오른쪽 또는 아래쪽으로 한 칸만 이동할 수 있다. WOOK은 자신이 위치한 (x,y)에 자원이 있는 경우에만 해당 자원을 채취할 수 있다. WOOK이 탐사할 영역에 대한 정보가 주어질 때, WOOK이 탐색할 수 있는 자원의 최대 숫자를 구하는 문제다.
문제 탐색하기
- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정
ex. 가능한 시간 복잡도, 알고리즘 선택
입출력 제한
- 1 ≤ N, M ≤ 300
처음엔 DFS로 풀어봤는데, 메모이제이션도 쓰지 않고 재귀 함수로 구현해서 그런지 시간 초과가 났다.
DP로 구현하려면 각 위치에 도달했을 때 얻은 최대 자원 수를 저장하는 배열을 만들고, 1행과 1열을 초기화한 뒤 나머지 값을 채워넣으면 된다. 오른쪽이나 아래쪽 말고 다른 방향으론 이동할 수 없기 때문에 dp[i][j]의 값은 dp[i-1][j]와 dp[i][j-1] 중 더 큰 값에 (i,j)에 자원이 있다면 1을 더한 값으로 볼 수 있다.
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + (board[i][j] ? 1 : 0)
이때, 삼항 연산자를 사용하는 경우 괄호로 묶어둬야 더 정확하게 계산할 수 있다.
- 예를 들어 dp[i-1][1] + board[i][1] ? 1 : 0;의 경우, ?보다 +가 우선이라 {dp[i-1][1] + board[i][1]} ? 1 : 0;로 계산돼서 dp 배열이 모두 1로 계산된다.
코드 설계하기
위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!
- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지
- N, M, 자원 정보 입력받기
- dp 배열 초기화하기
- dp 배열 = 각 위치에 도달했을 때 얻은 최대 자원 수를 저장하는 배열
- (1,1) ~ (1,M)과 (1,1) ~ (N,1) 초기화하기
- dp 배열 채우기
- (2,2) ~ (N,M)을 채우면서 진행하기
- 점화식 → dp[i][j] = max(dp[i-1][j],dp[i][j-1]) + board[i][j]
- dp[N][M] 출력하기
시도 회차 수정 사항 (Optional)
- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!
1회차
- 시간 초과 (DFS 알고리즘 사용)
정답 코드
#include <iostream>
using namespace std;
int n,m,mx,dp[301][301];
bool board[301][301];
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i=1; i<=n; i++)
for (int j=1; j<=m; j++) cin >> board[i][j];
dp[1][1] = (board[1][1]?1:0);
for (int i=2; i<=n; i++) dp[i][1] = dp[i-1][1]+(board[i][1]?1:0);
for (int i=2; i<=m; i++) dp[1][i] = dp[1][i-1]+(board[1][i]?1:0);
for (int i=2; i<=n; i++)
for (int j=2; j<=m; j++)
dp[i][j] = max(dp[i-1][j],dp[i][j-1])+(board[i][j]?1:0);
cout << dp[n][m];
}