글 읽기 - 반례 하나를 발견했는데, 이해가 가지 않아 질문 드립니다.

hyeok5596 2년 전 0

질문 게시판에 올라온 대부분의 반례에 대해서는 정답이지만,

아래와 같은 반례를 발견했습니다.

10
0 0 64 32 32 0 0 0 0 0
0 32 32 64 0 0 0 0 0 0
0 0 128 0 0 0 0 0 0 0
64 64 128 0 0 0 0 0 0 0
0 0 64 32 32 0 0 0 0 0
0 32 32 64 0 0 0 0 0 0
0 0 128 0 0 0 0 0 0 0
64 64 128 0 0 0 0 0 0 0
128 32 0 0 0 0 0 0 0 0
0 0 128 0 0 0 0 0 0 0

answer : 1024

my result : 512

일단 위의 반례에서 최소 6번은 이동해야 1024라는 값을 얻어낼 수 있을 것 같은데

어떻게 5번 안에 1024라는 값을 얻어낼 수 있는지를 모르겠습니다.

그리고 아래와 같은 백트래킹 방식으로 구현했는데 어느 부분이 논리적으로 틀린 부분인지 찾을 수가 없습니다.

static void allMove(int[][] block, int moveCnt) {

if(moveCnt == 5)
return;

upMove(block, moveCnt);
downMove(block, moveCnt);
leftMove(block, moveCnt);
rightMove(block, moveCnt);
}

전체 소스 코드 첨부합니다.

도움 요청드립니다. 감사합니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int maxValue = 2, n;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());

        int[][] block = new int[n + 1][n + 1];

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                block[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 0; i < n + 1; i++) {
            for (int j = 0; j < n + 1; j++) {
                maxValue = Math.max(maxValue, block[i][j]);
            }
        }

        allMove(block, 0);

        System.out.println(maxValue);
    }


    static void upMove(int[][] block, int moveCnt) {
        int[][] copiedArray = copyArray(block);
        boolean[][] merged = new boolean[n + 1][n + 1];
        /*
        블록을 위로 이동하는 부분 구현
         */

        for (int i = 1; i < n; i++) {
            for (int j = i; j > 0; j--) {
                for (int k = 0; k < n; k++) {

                    if(copiedArray[j-1][k] == 0) {
                        copiedArray[j-1][k] = copiedArray[j][k];
                        copiedArray[j][k] = 0;
                    }
                    else if(!merged[j-1][k] && copiedArray[j][k] == copiedArray[j-1][k]) {
                        copiedArray[j-1][k] *= 2;
                        copiedArray[j][k] = 0;
                        maxValue = Math.max(copiedArray[j-1][k], maxValue);
                        merged[j-1][k] = true;

                    }


                    }
                }
            }
        allMove(copiedArray, moveCnt + 1);
        }


    static void downMove(int[][] block, int moveCnt) {
        int[][] copiedArray = copyArray(block);
        boolean[][] merged = new boolean[n + 1][n + 1];

        /*
        블록을 아래로 이동하는 부분 구현
         */

        for (int i = n - 2; i >= 0; i--) {
            for (int j = i; j <= n - 2; j++) {
                for (int k = 0; k < n; k++) {

                    if (copiedArray[j + 1][k] == 0) {
                        copiedArray[j + 1][k] = copiedArray[j][k];
                        copiedArray[j][k] = 0;
                    }

                    else if (!merged[j + 1][k] && copiedArray[j][k] == copiedArray[j + 1][k]) {
                        copiedArray[j + 1][k] *= 2;
                        copiedArray[j][k] = 0;
                        maxValue = Math.max(copiedArray[j + 1][k], maxValue);
                        merged[j + 1][k] = true;
                    }
                }
            }
        }
        allMove(copiedArray, moveCnt + 1);

    }

    static void leftMove(int[][] block, int moveCnt) {
        int[][] copiedArray = copyArray(block);
        boolean[][] merged = new boolean[n + 1][n + 1];

        /*
        블록을 왼쪽으로 이동하는 부분 구현
         */

        for (int i = 1; i < n; i++) {
            for (int j = i; j > 0; j--) {
                for (int k = 0; k < n; k++) {

                    if (copiedArray[k][j-1] == 0) {
                        int tmp = copiedArray[k][j];
                        copiedArray[k][j] = 0;
                        copiedArray[k][j-1] = tmp;

                    }

                    else if(!merged[k][j-1] && copiedArray[k][j] == copiedArray[k][j - 1]) {
                        copiedArray[k][j-1] *= 2;
                        copiedArray[k][j] = 0;
                        maxValue = Math.max(copiedArray[k][j - 1], maxValue);
                        merged[k][j - 1] = true;
                    }
                }
            }
        }

        allMove(copiedArray, moveCnt + 1);

    }

    static void rightMove(int[][] block, int moveCnt) {
        int[][] copiedArray = copyArray(block);
        boolean[][] merged = new boolean[n + 1][n + 1];
        /*
        블록을 오른쪽으로 이동하는 부분 구현
         */

        for (int i = n - 2; i >= 0; i--) {
            for (int j = i; j < n - 1; j++) {
                for (int k = 0; k < n; k++) {

                    if (copiedArray[k][j+1] == 0) {
                        int tmp = copiedArray[k][j];
                        copiedArray[k][j] = 0;
                        copiedArray[k][j+1] = tmp;

                    }

                    else if(!merged[k][j + 1] && copiedArray[k][j] == copiedArray[k][j + 1]) {
                        copiedArray[k][j + 1] *= 2;
                        copiedArray[k][j] = 0;
                        maxValue = Math.max(copiedArray[k][j + 1], maxValue);
                        merged[k][j+1] = true;
                    }
                }
            }
        }
        allMove(copiedArray, moveCnt + 1);

    }

    static void allMove(int[][] block, int moveCnt) {

        if(moveCnt == 5)
            return;

        upMove(block, moveCnt);
        downMove(block, moveCnt);
        leftMove(block, moveCnt);
        rightMove(block, moveCnt);
    }

    static int[][] copyArray(int[][] block) {
        int[][] copiedArray = new int[n + 1][n + 1];

        for (int i = 0; i < n + 1; i++) {
            for (int j = 0; j < n + 1; j++) {
                copiedArray[i][j] = block[i][j];
            }
        }

        return copiedArray;
    }
}

papower1 1년 전 3

저도 아직 이 문제를 풀지 못해 여러 예제를 대입해보는 중인데용.

예시로 든 문제는 5번에 1024가 가능함을 확인하였습니다.

아래는 제 결과입니다.

---

initial

0 0 64 32 32 0 0 0 0 0

0 32 32 64 0 0 0 0 0 0

0 0 128 0 0 0 0 0 0 0

64 64 128 0 0 0 0 0 0 0

0 0 64 32 32 0 0 0 0 0

0 32 32 64 0 0 0 0 0 0

0 0 128 0 0 0 0 0 0 0

64 64 128 0 0 0 0 0 0 0

128 32 0 0 0 0 0 0 0 0

0 0 128 0 0 0 0 0 0 0

right

0 0 0 0 0 0 0 0 64 64

0 0 0 0 0 0 0 0 0 128

0 0 0 0 0 0 0 0 128 128

0 0 0 0 0 0 0 0 64 64

0 0 0 0 0 0 0 0 0 128

0 0 0 0 0 0 0 0 128 128

0 0 0 0 0 0 0 0 128 32

0 0 0 0 0 0 0 0 0 128

top

0 0 0 0 0 0 0 0 128 128

0 0 0 0 0 0 0 0 128 256

0 0 0 0 0 0 0 0 128 128

0 0 0 0 0 0 0 0 256 256

0 0 0 0 0 0 0 0 0 32

0 0 0 0 0 0 0 0 0 128

0 0 0 0 0 0 0 0 0 0

right

0 0 0 0 0 0 0 0 0 256

0 0 0 0 0 0 0 0 128 256

0 0 0 0 0 0 0 0 0 256

0 0 0 0 0 0 0 0 0 512

0 0 0 0 0 0 0 0 0 32

0 0 0 0 0 0 0 0 0 128

0 0 0 0 0 0 0 0 0 0

down

0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 256

0 0 0 0 0 0 0 0 0 512

0 0 0 0 0 0 0 0 0 32

0 0 0 0 0 0 0 0 128 128

top

0 0 0 0 0 0 0 0 128 256

0 0 0 0 0 0 0 0 0 1024

0 0 0 0 0 0 0 0 0 32

0 0 0 0 0 0 0 0 0 128

0 0 0 0 0 0 0 0 0 0

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례 하나를 발견했는데, 이해가 가지 않아 질문 드립니다.

hyeok5596 2년 전 0

papower1 1년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말