[코딩 테스트 RUN] SWEA RUN : 26071. 블록 제거 게임

 

⚠️ 주의!
SWEA에서 낸 코딩 문제에 대한 해답이 들어있습니다.
열람 시 주의해주세요.

 

강사님이 추천해주신 문제인데 재귀를 쓰지 않으면 답이 안 나오는 문제다.

재귀는 정말 많이 어려운데 덕분에 메서드를 써야한다는 생각을 드디어 하기 시작했다(나중에 다룰 동영상 재생기도 이 덕분에 풀었고…)

 

[SW Expert Academy] 26071. 블록 제거 게임

SW Expert Academy

 

메서드를 분리하지 않고는(재귀를 통해서가 아니면) 절대 풀지 못하는 문제에 가깝다(가능은 한데 너무 많은 메모리와 연산이 든다.) 이번에도 여러 번의 시행착오와 설계 파기가 있어 과정을 적어본다.

 

 

문제에 대한 과정

첫 번째는 바로 "최대수"를 기점으로 왼쪽과 오른쪽 중 작은 걸 깨는, 일종의 그리디 방식이다. 왜냐하면 최대한 최대수를 남겨두는 것이 곱셈에 유리하기 때문이다. 그러나 이 방식은 틀렸다. 왜냐하면 반드시 그게 최대점수를 낸다는 보증이 없기 때문이다. 결국 DFS/재귀 방식으로 전체 탐색을 해야하는데, 처음에는 DFS로 시작했다. 다만 문제는 "블록을 깨는 과정"의 반복이다. 이것을 하나의 함수(메서드) 안에서 해결할 수는 없다. 블록은 계속해서 깨져야하고, 그것들의 max값을 또 갱신해야하기 때문이다. 이건 한 번의 과정으로는 불가능하다.

 

일단 static으로 maxScore라는 전역 변수를 만들었다. 이것이 앞으로 maxScore를 담아줄 것이다.

그리고 blockRemove라는 메서드를 만들었다. 여기에 list를 사용했는데, 왜냐하면 블록의 개수가 가변적이기 때문이다.

인자로는 리스트를 넣고, 시작 max값은 0으로 넣는다.

그리고 내가 넣은 blockRemove는 이렇게 된다.

 

    static void blockRemove(ArrayList<Integer> list, int max){
    
        if(list.size() == 1){
            max += list.get(0);
            maxScore = Math.max(maxScore, max);
            return;
        }

        for(int i = 0; i < list.size(); i++){
            int left = 1, right = 1;

            if(i - 1 >= 0) { left = list.get(i - 1); }
            if(i + 1 < list.size()) { right = list.get(i + 1); }
            int score = left * right;

            int removed = list.remove(i);
            blockRemove(list, max + score);
            list.add(i, removed);

        }

    }

 

천천히 살펴보면, list.size가 1이 되면(즉 블록이 자기자신만이 남으면), 자기자신을 추가하여 maxScore를 확인하고 return한다. 여기서 maxScore가 전역변수인 이유가 바로 이 때문이다. maxScore값을 클래스 전체에 저장해둬야하기 때문이다. 그 다음을 보자. list.size를 하는데, 왼쪽과 오른쪽 블록을 확인하고 score를 그 왼쪽과 오른쪽 값에 넣어 곱한다. 왼쪽이나 오른쪽이 없다면 없는 셈으로 치고 기본값인 1로 사용하면 되는 것이다. 그리고 여기서 도움을 받은 부분은 바로 remove. remove는 삭제한 것을 반환해준다. 그러므로 이 removed의 값을 받아, list.add에 삭제된 녀석을 다시 추가한다.

일단 그 전에 다시 재귀를 실행하는데, 블록 값을 깨는 걸 반복하기 위해서다. 만약에 이 블록깨기가 끝나면, 제거했던 removed를 다시 원상복구한다.

 

너무 복잡한 과정인데, 이미지로 나타내면 이런 느낌이다.

 

 

 

정답

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;


public class Solution {
    static int maxScore = 0;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for(int test_case = 1; test_case <= T; test_case++) {
            // 각 테스트 케이스 시작
            int N = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine());
            ArrayList<Integer> list = new ArrayList<>();
            for (int i = 0; i < N; i++) {
                list.add(Integer.parseInt(st.nextToken()));
            }

            maxScore = 0;
            blockRemove(list,0);

            System.out.printf("#%d %d%n", test_case, maxScore);
        }
    }

    static void blockRemove(ArrayList<Integer> list, int max){
    
        if(list.size() == 1){
            max += list.get(0);
            maxScore = Math.max(maxScore, max);
            return;
        }

        for(int i = 0; i < list.size(); i++){
            int left = 1, right = 1;

            if(i - 1 >= 0) { left = list.get(i - 1); }
            if(i + 1 < list.size()) { right = list.get(i + 1); }
            int score = left * right;

            int removed = list.remove(i);
            blockRemove(list, max + score);
            list.add(i, removed);

        }

    }

}