BOJ
BOJ::2169 로봇 조종하기
BOJ Gold 1
BOJ::2169 로봇 조종하기
- Link : BOJ::2169
- Level : Gold 1
시사점
- 좋은 DP 문제입니다.
- 설계에만 47분을 사용한 문제이고, 풀고나서 다른 사람들 풀이를 보니, 제 풀이는 naive하여 O(N^3)인
반면, 다들 O(N^2)으로 풀었습니다.
- 차이점은 좋은코드 챕터에서 설명하겠습니다.
- 중요한 것은, 제 DP 풀이 수준이 낮아서이겠지만,
- 이렇게 병렬로 for문을 배치하여 풀면 복잡도가 현저히 줄어들지만,
- 대부분 직렬로 연결하여 푼다는 점입니다.
- DP문제도 많은 공부가 필요할 것 같습니다.
키
이해(10)
- (1,1)에서 시작해서 (N,M)에 도착하는 모든 경로 중 도착점의 값이 최대가 되도록 하는 경로의 합을
출력합니다.
- 단, 정점 이동은 좌/우/하 방향으로만 가능합니다.
설계, 손 코딩(37)
- 손으로 중심이 되는 코드를 구현합니다.
- 경로탐색 문제임에도 불구하고 N의 값이 10^3이나 됩니다.
- graph탐색 중 가능한 방법이 있는지 생각해보았지만, 다익스트라도, 플로이드도 불가능합니다.
- 따라서, naive하게 접근하기 위해 손으로 직접 방향성을 그려보며 고민을 하였습니다.
- 결론은 다음과 같습니다.
- 첫번째 행
- 첫번째 행에서는 우측방향만 가능합니다.
- 중간 행들
- 각 행마다, 각 열마다 진행합니다.
- 정해진 행과 열을row, pos라고 할때, pos로 오는 경로는 다음과 같습니다.
- [row-1][pos]에서 바로 내려오는 경우,
- [row-1][pos-1]에서 내려와서, [row][pos-1]을 거쳐오는 경우
- [row-1][pos-2]에서 내려와서, [row][pos-2]를 거치고, [row][pos-1]을 거쳐오는 경우,
- …
- 위의 과정에서 볼 수 있듯이, 현재 정점으로 오는 경로를 생각해보면,
- 좌측이든 우측이든 그 위에 있는 행부터 시작해서 한칸 내려와서 방향을 꺾어서 현재 정점으로 오는 경우 입니다.
- 각 행마다, 각 열마다 진행합니다.
- 마지막 행
- 마지막행도 중간행들처럼 처리합니다.
- 단, 우측방향에 대해서만 수행합니다.
- 첫번째 행
시간 복잡도
공간 복잡도
손 코딩 후 문제 리뷰(x)
- 빼먹고 손 코딩 한 것이 있는지 확인합니다.
구현(33)
함수 List
업데이트 되는 변수
- 대부분의 디버깅 문제는 업데이트 되는 변수에서 발생합니다.
실제 구현
- 해당 코드는 1072ms 에 통과합니다.
#include<bits/stdc++.h>
#define endl '\n'
#define rep(i,a,b) for(int i=a;i<b;i++)
#define r_rep(i,a,b) for(int i=a;i>b;i--)
const int MAXNM = 1000;
const int INF = 987654321;
using namespace std;
int n, m;
int a[MAXNM][MAXNM];
int dp[MAXNM][MAXNM];
void solve(){
/* 0 행 : 우측 방향만 존재 */
dp[0][0] = a[0][0];
int accum = a[0][0];
rep(j, 1, m){
dp[0][j] = a[0][j] + accum;
accum += a[0][j];
}
/* [1, n-2]행 : 좌 우 모두 존재 */
rep(i, 1, n-1){
rep(pos, 0, m){
int mx = -1 * INF;
accum = 0;
r_rep(j, pos-1, -1){
int sum = dp[i-1][j] + a[i][j] + accum;
mx = max(mx, sum);
accum += a[i][j];
}
accum = 0;
rep(j, pos+1, m){
int sum = dp[i-1][j] + a[i][j] + accum;
mx = max(mx, sum);
accum += a[i][j];
}
dp[i][pos] = max(mx , dp[i-1][pos]) + a[i][pos];
}
}
/* n-1행 : 우측 방향만 존재 */
if(n > 1){
rep(pos, 0, m){
int row = n-1;
int mx = -1 * INF;
accum = 0;
r_rep(j, pos-1, -1){
int sum = dp[row-1][j] + a[row][j] + accum;
mx = max(mx, sum);
accum += a[row][j];
}
dp[row][pos] = max(mx , dp[row-1][pos]) + a[row][pos];
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n>> m;
rep(i, 0, n) rep(j, 0, m) cin >> a[i][j];
solve();
cout << dp[n-1][m-1] << endl;
return 0;
}
구현 후 코드리뷰 + 예제 돌려보기(x)
- 바로 예제를 넣어서 테스트 해보기 전에, 코드를 한 번 리뷰하고, 예제의 입력이 이런식으로 왔을때 전체 코드가 어떤 식으로 순차적으로 진행되는지 답은 잘 도출될 것 같은지 확인합니다.
디버깅(x)
좋은 코드
- 행과 열은 1부터 시작하도록 코드를 수정하였고, O(N^2)으로 변형시켰습니다.
- 해당 코드는 84ms에 통과합니다.
- 열의 범위는 [1,m]입니다.
- 하지만 열을 확장하여 0번째 열과 m+1번째 열을 추가로 사용하는 것을 눈여겨봐야 합니다.
- tmp[0][j] 에 좌측방향에서부터 축적되어온 값과 위에서 바로 내려온 값을 비교하여 대입합니다.
- tmp[1][j] 에 우측방향에서부터 축적되어온 값과 위에서 바로 내려온 값을 비교하여 대입합니다.
- 본문의 풀이법과 하기의 풀이법은 결국 현재정점에 올 수 있는 최댓값은,
- 위에 행에서 온 dp값과 현재 행에서 온 a값(정점의 값)의 합으로만 나타낼 수 있기에 가능합니다.
- 즉, 현재 행에서도 dp가 사용되어야 하는 경우엔 해당 방법을 사용할 수 없습니다.
- 그렇게 된다면, 한 행에 존재하는 각 점들은 interactive하기때문입니다.
void solve(){
/* 0 행 : 우측 방향만 존재 */
dp[1][1] = a[1][1];
int accum = a[1][1];
rep(j, 2, m+1){
dp[1][j] = a[1][j] + accum;
accum += a[1][j];
}
int tmp[2][MAXNM+1]={0};
rep(i, 2, n+1){
tmp[0][0] = dp[i-1][1];
rep(j, 1, m+1) tmp[0][j] = max(tmp[0][j-1], dp[i-1][j]) + a[i][j];
tmp[1][m+1] = dp[i-1][m];
r_rep(j, m, 0) tmp[1][j] = max(tmp[1][j+1], dp[i-1][j]) + a[i][j];
rep(j, 1, m+1) dp[i][j] = max(tmp[0][j], tmp[1][j]);
}
}