백준 2240 자두나무

백 2240 자두나무

---

• 이번 문제는 자두나무이다. dp 를 이용해야 하는데, 문제에서 나오는 조건들을 배열로 만들어 저장해오면 된다.

for (int i = 1; i <= t; i++) {
            for (int j = 1; j <= w+1; j++) {
                if (arr[i] == 1) {
                    table[1][i][j] = Integer.max(table[1][i - 1][j] + 1, table[2][i - 1][j - 1] + 1);
                    table[2][i][j] = Integer.max(table[1][i - 1][j - 1], table[2][i - 1][j]);
                    ans.add(table[1][i][j]);
                    ans.add(table[2][i][j]);
                } else {
                    if (i == 1 && j == 1) {
                        continue;
                    }
                    table[1][i][j] = Integer.max(table[1][i-1][j], table[2][i-1][j-1]);
                    table[2][i][j] = Integer.max(table[1][i-1][j-1] + 1, table[2][i-1][j] + 1);
                    ans.add(table[1][i][j]);
                    ans.add(table[2][i][j]);
                }
            }
        }

• 코드를 보면, 자두가 1번 나무에 있을 때, 2번 나무에 있을 때에 대해 이전의 순서에서
  참고해야할 나무가 바뀐다. 만약 1번 나무에 자두가 있다면, 1번나무에 계속 있던 경우, 2번 나무에서 이동해 오는 경우가 두가지가 있겠다.
  그 경우에 대해 전부 max 값을 저장해 오면 된다.

if (i == 1 && j == 1) {     
    continue;
}

• 이 부분은 처음부터 2번 나무로 이동하는 경우에 대한 케이스이다.
• w+1 만큼 이동하는 경우는, 3번 이동이 가능할 경우 0,1,2,3 만큼 이동할 수 있기 때문이다.