[14722]우유도시(java)

문제보기

편의상 딸기우유를 0번, 초코우유를 1번, 바나나우유를 2번이라 하겠다

1. 마지막으로 마신 우유 정보를 가지고 있어야한다.

그래서 3차원 배열로 설정하는 것이 좋다. x좌표, y좌표, 그리고 구매한 우유정보를 각 차원에다가 저장한다.

for(int k=0;k<3;k++){
    // 우유 미구매했을 때 => 이전에 마신 우유상태를 그대로 유지할 것
    dt[k][i][j] = Math.max(
        dt[k][i-1][j], dt[k][i][j-1]
    );
}

(i,j)좌표에서 마지막으로 k번 우유를 마신 상태를 3차원 배열로 저장한 것이다.

2. 이전에 우유를 구매하지 않으면 다음 우유도 구매할 수 없다

1번 우유를 구매하기 위해서는 0번 우유를 이전에 구매했어야한다.
2번 우유를 구매하기 위해선 1번 우유를 이전에 구매했어야한다.
0번 우유는 예외이다.

int k = arr[i][j];
int tmp = k == 0 ? 2 : k-1;
if(k==0 || dt[tmp][i-1][j] != 0){
    // 0번 우유는 언제든 구매 가능
    // 그 외의 우유의 경우 이전에 구매내역이 있어야 구매가능
    dt[k][i][j] = Math.max(
            dt[k][i][j], dt[tmp][i-1][j]+1
    );
}
if(k==0 || dt[tmp][i][j-1] != 0){
    dt[k][i][j] = Math.max(
            dt[k][i][j], dt[tmp][i][j-1]+1
    );
}

k는 지금 판매하는 우유의 번호이고, tmp는 k번 우유를 마시기 위해 이전에 구매해야하는 우유의 번호이다.
(즉 k가 1이라면, tmp는 0이다.)

dt[tmp][i-1][j] 또는 dt[tmp][i][j-1]가 0이라는 것을 검사하는 것이 중요하다.

(3,3)좌표에서 1번우유를 파는 경우 (3,2)나 (2,3)에서 0번 우유를 마신 상태여야만 1번 우유를 구매할 수 있다.

조건문 앞에 k==0 조건이 붙는 이유는 다음 이유 때문이다.

3. 0번 우유를 가장 먼저 사야한다

3-1. 첫번째 우유가게에서 0번 우유를 팔지 않는 경우가 있다
3-2. 0번 우유를 사지 못했다면 그 어떤 우유도 구매할 수 없다.
3-3. 반대로 언제든지 0번 우유는 구매할 수 있다(제일 처음으로 구매할 수 있는 우유이므로)

3-1. 문제의 예제에서는 1,1 좌표에서 항상 0번 우유를 판매하지만,
안타깝게도 문제에 그런 조건은 없다. 0번 우유를 아예 판매하지 않는 경우도 있을 수 있다.

3-2. 2번에서 이전 좌표에서 0번 우유를 마셨는지 체크했으므로 해결되었다.

3-3. k==0 조건이 붙어야하는 이유이다. 0번 우유는 언제든지 구매할 수 있다.

(3,2)에서 0번 우유를 마시지 않았다면 (3,3)좌표에서 1번 우유를 구매할 수 없지만,
(3,2)에서 2번 우유를 마시지 않았어도 (3,3)에서 0번 우유를 구매할 수 있다.

코드

int[][][] dt = new int[3][n+1][n+1];

for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
        for(int k=0;k<3;k++){
            // 우유 미구매했을 때 => 이전에 마신 우유상태를 그대로 유지할 것
            dt[k][i][j] = Math.max(
                dt[k][i-1][j], dt[k][i][j-1]
            );
        }
        int k = arr[i][j];
        int tmp = k == 0 ? 2 : k-1;
        if(k==0 || dt[tmp][i-1][j] != 0){
            // 0번 우유는 언제든 구매 가능
            // 그 외의 우유의 경우 이전에 구매내역이 있어야 구매가능
            dt[k][i][j] = Math.max(
                    dt[k][i][j], dt[tmp][i-1][j]+1
            );
        }
        if(k==0 || dt[tmp][i][j-1] != 0){
            dt[k][i][j] = Math.max(
                    dt[k][i][j], dt[tmp][i][j-1]+1
            );
        }
    }
}


int ans = -1;
for(int k=0;k<3;k++){
    ans = Math.max(dt[k][n][n], ans);
}

입출력 부분 빼고 문제 풀이 부분만 담으면 이렇게 된다.