프로그래머스(종이접기) - Java

[종이 접기]

https://programmers.co.kr/learn/courses/30/lessons/62049

코딩테스트 연습 - 종이접기

 

* 로직

• n번째 접었을 때 나오는 값은 맨 처음 접히는 가운데(0)을 기준으로 규칙성이 나타난다
  • 왼쪽엔 이전 n-1번째 접었을 때 나오는 값
  • 오른쪽엔 왼쪽에 있는 값의 보수이다
• 이를 기반으로 dp를 진행한다 (dp[1] = 0)
• n=2부터 위의 규칙대로 포문 로직을 진행해준다

 

class Solution {
    public int[] solution(int n) {
        int[] answer = {};
        String[] dp = new String[n+1];
        dp[1] = "0";

        for(int i=2; i<=n; ++i){
            StringBuilder sb = new StringBuilder(dp[i-1]);
            sb.append("0");
            for(int s=dp[i-1].length()-1; s>=0; --s) {
                if(dp[i-1].substring(s, s+1).equals("0")) sb.append("1");
                else sb.append("0");
            }
            dp[i] = sb.toString();
        }

        answer = new int[dp[n].length()];
        for(int i=0; i<dp[n].length(); ++i) {
            answer[i] = Integer.parseInt(dp[n].substring(i, i+1));
        }
        return answer;
    }
}