[백준 03991] 한번 쏘면 멈출 수 없어 [Java]

문제

https://www.acmicpc.net/problem/3991

 

---

풀이

문제의 규칙에 따라 구슬들을 없애면서 최대 점수를 구하는 문제다.

최대 점수를 얻기 위해서는 종류가 C개인 구슬들을 종류 별 로 한 턴에 전부 없애면 된다.

그러기 위해서는 구슬을 아래에서 위로, 왼쪽에서 오른쪽으로 계단을 쌓듯 구슬을 배치하면 된다.

        // Solve
        int idx = 0;
        for (int j = 0; j < w; ++j) {
            for (int i = h - 1; i >= 0; --i) {
                if (color[idx] <= 0) {
                    ++idx;
                }
                A[i][j] = idx + 1;
                --color[idx];
            }
        }

이제 오른쪽 위부터 구슬을 제거하면 남아있는 구슬들의 위치가 바뀌지 않으면서도 한 턴에 한 종류의 구슬을 모두 제거할 수 있다.

 

풀이 시간

≤ 13m

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/easy/03991.java

problem-solving/baekjoon-online-judge/easy/03991.java at main · rogi-rogi/problem-solving