프로그래머스(타일 장식물, 4단 고음) - Java

[타일 장식물]

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

코딩테스트 연습 - 타일 장식물

 

* 조건

1. 타일은 나선형 형태로 변의 길이를 늘려가며 점점 커진다
2. 늘어날수록 타일의 변의 길이는 1, 1, 2, 3, 5, 8 ... 식으로 늘어난다
3. 타일의 개수 N이 주어졌을 때, 해당 타일에서 만들 수 있는 가장 큰 사각형의 둘레를 출력한다

* 알고리즘

- DP

 

* 로직(Logic)

- 사각형 1개로 만들 수 있는 둘레길이부터 2개 3개 .. 을 구하다보면 4, 6, 10, 16, 26 ... 이 나열된다

- 이를 통해 dp[i] = dp[i-2] + dp[i-1] 점화식을 도출할 수 있다

 

package me.uyoo.GroupPractice.Programmers.Level;

public class Problem_Tile {

    public static void main(String[] args) {
        int n = 6;
        long answer = solution(n);
        System.out.println(answer);
    }

    public static long solution(int N) {
        long answer = 0;
        long[] dp = new long[N+1];
        dp[1] = 4;
        dp[2] = 6;
        for(int i=3; i<=N; ++i){
            dp[i] = dp[i-2] + dp[i-1];
        }
        answer = dp[N];

        return answer;
    }
}

 

---

[4단 고음]

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

코딩테스트 연습 - 4단 고음

 

* 조건

1. 3단 고음은 *++ 형태로 표현한다
2. 3단 고음 내에서 또 다시 3단 고음을 낼 수 있다 (ex. **++++)
3. *: 곱하기 3, +: 더하기 1 이고, 시작 음 높이: 1이다
4. 주어진 음 높이 n을 달성할 수 있는 서로 다른 문자열의 개수를 출력한다

* 알고리즘

- 만들 수 있는 경우의 수를 탐색: 브루트 포스

 

* 로직(Logic)

- 거꾸로 생각해보면 맨 끝 2자리는 ++로 이루어져야 하고, 맨 앞은 *로 이루어져 있어야 한다

- 덧셈기호를 카운팅하면서 주어진 n의 값을 1씩 빼주고, 덧셈이 2개 이상이면서 3으로 나누어 떨어지는 순간이 오면 곱하기(*)가 사용되었다고 생각한다. 이 순간 덧셈기호를 -2 차감시켜주면 된다

 

- 이를 재귀적으로 반복한다 (하지만 n의 사이즈가 5이상 2^31-1이하이기 때문에 제약 조건을 설정하는게 까다로웠다)

- 카운팅되는 덧셈 개수를 이용해 현재 차감된 n의 값을 만들 수 있는지 여부를 판단하면 된다

ex. 덧셈 개수: 4개, n=6 이라면 -> ++++가 있는 상태이고
이 상태에서 4/2 = 2는 *이 놓일 수 있는 개수이다. 즉, **++++를 만들게 되는 것이고 3^2 = 9점은 최소로 있어야 3단 고음을 완성시킬 수 있다는 것이다.

 

- Math.pow(3, 덧셈 개수/2) > n 이라면 음 높이를 만들 수 없기 때문에 return을 시키면 된다

 

public class Problem_FourspeedTreble_ {

    public static void main(String[] args) {
        int n = 2147483647;
        int ans = solution(n);
        System.out.println(ans);
    }

    public static int solution(int n) {
        int answer = 0;
        long addCnt = 0;
        answer = doProcess(addCnt, n);

        return answer;
    }

    private static int doProcess(long addCnt, int n) {
        if(Math.pow(3, addCnt/2)>n) return 0;

        int count = 0;
        if(n == 3){
            if(addCnt == 2) return 1;
            return 0;
        }
        else if(n > 3){
            if(addCnt >= 2 && (n % 3) == 0) {
                count += doProcess(addCnt-2, n/3);
            }
            count += doProcess(addCnt+1, n-1);
        }

        return count;
    }
}