[프로그래머스] 종이 접기 (07.23)

문제

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

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

 

접근법

규칙을 찾아서 dp를 적용시켰다

dp[n] = dp[n-1] + "0" + reverse(dp[n-1])

라는 점화식을 도출해내고

reverse라는 메소드를 따로 만들어서 빼주었다.

전에는 재귀로 풀었는데 이번에는 dp로 풀었당!! 

 

코드

class Solution {
    public int[] solution(int n) {
        String[] dp = new String[n];

        dp[0] = "0";
        for(int i=1;i<n;i++){
            dp[i] = dp[i-1] + "0" + reverse(dp[i-1]);
        }

        int[] answer = new int[dp[n-1].length()];

        for(int i=0;i<answer.length;i++){
            answer[i] = dp[n-1].charAt(i) -'0';
        }

        return answer;
    }

    private String reverse(String s) {
        char[] chars = s.toCharArray();
        //1을 0으로, 0을 1로 바꿔주고
        for(int i=0;i<chars.length;i++){
            if(chars[i] == '1')
                chars[i] = '0';
            else
                chars[i] = '1';
        }

		//역순으로 정렬
        StringBuilder sb = new StringBuilder();
        for(int i=chars.length-1; i>=0; i--){
            sb.append(chars[i]);
        }

        return sb.toString();
    }   
}