프로그래머스 Lv.3) 종이접기

종이접기

프로그래머스

풀이

(코드 1, 코드 2)

 

문제를 보자마자 점화식이 필요한 문제라고 생각했다. 그래서 처음 생각한 점화식은 n => n-1까지의 결과를 두 번 반복하고 끝에 1이 들어간다고 생각했다. 주어진 테스트 케이스만 봤을 때는 답이 나오기는 했다. 하지만 제출 결과는 0점이었다. 점화식이 틀렸다는 것을 알아차리고 새로운 점화식을 세우려했다. 하지만 어제 과음..  다른 분의 점화식을 참고하니까 2^(n-1)을 기준으로 대칭되는 인덱스는 서로 다른 값을 가지고 있다는 식을 보았다. 물론 기준점(2^(n-1)) 이전 까지는 n-1의 결과값을 똑같이 가지고 있다.

하나의 테스트 케이스를 가지고 설명을 하면,

n=3 일 때, [0,0,1,0,0,1,1]의 결과 값이 나오는데 2^(n-1)인 4번 째 값 ~> Idx:3 번을 기준으로 idx 2번과 4번이 서로 다른값을 가지고, 1번과 5번이 다른값, 0번과 6번이 다른값을 가진다.

 

---

2020.06.03) 코드 3

 

다시 풀었을 때는 수월하게 풀었다. 로직이 머리에 남아있어서 그런 부분도 있지만, 위의 점화식이 이해가 갔다.

문제에서 종이의 오른쪽 면을 왼쪽으로 반을 접는 행위를 N번 반복한다는 조건이 있다.

이 때문에 left와 right가 서로 반대의 주름을 가지게 된다.

또한, 접힌 상태에서 한번 더 접게되면, n-1에 가지고 있던 주름이 n번째의 왼쪽에 주름이 가게 된다.

이를 이용해 조금 더 쉽게 풀었다.

 

 

코드1

public class Origami_62049 {
    static int[][] answer;
    private static int[] solution(int n) {
        answer = new int[n][];
        makeArr(n);
        return answer[n-1];
    }

    private static void makeArr(int n) {
        for(int i=1; i<=n; i++) {
            answer[i-1] = new int[(int)Math.pow(2,i)-1];
            if(i !=1) {
                setAnswer(i);
            }
        }
    }

    private static void setAnswer(int num) {
        int addIdx = (int)Math.pow(2,num-1);

        for(int i=0; i<answer[num-2].length; i++) {
        	answer[num-1][i] =  answer[num-2][i];
            answer[num-1][addIdx+i] =  answer[num-2][i];
        }

        if(num != 1) {  // 마지막 IDX
            answer[num-1][(int)Math.pow(2,num)-2] =1;
        }
    }


    public static void main(String[] args) {
        int n = 4;
        int[] result = solution(n);
        for(int num : result) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

 

코드2

public class Origami_62049 {
    static int[][] answer;
    private static int[] solution(int n) {
        answer = new int[n][];
        makeArr(n);
        return answer[n-1];
    }

    private static void makeArr(int n) {
        for(int i=1; i<=n; i++) {
            answer[i-1] = new int[(int)Math.pow(2,i)-1];
            if(i !=1) {
                setAnswer(i);
            }
        }
    }

    private static void setAnswer(int num) {
        int addIdx = (int)Math.pow(2,num-1);
        int standard = (int)Math.pow(2, num-1) -1; // 기준점, 중간

        for(int i=0; i<standard; i++) { // 이 전 값 저장
            answer[num-1][i] = answer[num-2][i];
        }

        for(int i=1; i<=standard; i++) {	// 대칭되는 Idx에 반대 값 저장
            answer[num-1][standard+i] = getOpposNum(answer[num-1][standard-i]);
        }
    }

    private static int getOpposNum(int num) {	// 반대 값 return
        return num==0 ? 1 : 0;
    }

    public static void main(String[] args) {
        int n = 4;
        int[] result = solution(n);
        for(int num : result) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

 

코드 3

 

class Solution {
    public int[] solution(int n) {
        int[] answer = new int[(int)Math.pow(2,n)-1];
        if(n>1) {
            for(int i=1; i<=n; i++) {
                int standard = (int)Math.pow(2,i-1)-1;
                for(int j=1; j<=standard; j++) {
                    if(answer[standard-j] ==0) {
                        answer[standard+j] = 1;
                    } else {
                        answer[standard+j] = 0;
                    }
                }
            }
        }
        return answer;
    }
}