아찌방 하우스

문제

피보나치 수열은 아래와 같이 표현된다.

1, 1, 2, 3, 5, 8, 13, 21, 34, ...

각 숫자는 앞의 두 숫자의 합으로 나타내는 것을 알 수 있다.

P와 Q 그리고 n이 주어질 때, P번째 피보나치 숫자를 Q로 나눈 나머지를 구하여라. 

입력

첫 번째 라인에는 정수 T개의 테스트 케이스가 주어진다.

각 테스트 케이스는 정수 P와 Q가 주어진다.

출력

각 테스트 케이스마다 "Case #x: M" 형식으로 출력한다.

x는 테스트 케이스 번호(1부터 시작), M은 P번째 피보나치 숫자를 Q로 나눈 나머지이다.

제한

• 1 ≤ P ≤ 10,000
• 1 ≤ Q ≤ 2,000,000,000

코드

import java.math.BigInteger;
import java.util.*;
import java.io.*;

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

        int TC = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        BigInteger[] dp = new BigInteger[10001]; // P의 최댓값이 10000이기에

        dp[0] = BigInteger.valueOf(0);
        dp[1] = BigInteger.valueOf(1);

        for(int i = 2; i <= 10000; i++){
            dp[i] =  dp[i-2].add(dp[i-1]);
        }

        for(int tc = 1; tc <= TC; tc++){
            st = new StringTokenizer(br.readLine());

            int P = Integer.parseInt(st.nextToken());
            int Q = Integer.parseInt(st.nextToken());
            
            sb.append("Case #"+tc+": "+dp[P].remainder(BigInteger.valueOf(Q))+"\n");
        }
        System.out.print(sb);
    }
}

풀이

단순한 문제입니다!

다만 주의할 점이 2가지 있습니다.

1. P의 최댓값이 10000이라는 점

피보나치를 구하면 

int 형으로 하면 P 가 76 정도면 터집니다.

그런데

long, Long, double 이 int 형보다 사이즈가 훨씬 크다고 해도

10000의 피보나치를 구할 수 있을까요?

네!

없습니다!

저 위의 모든 형태의 변수를 사용해도 110 정도만 되면 다 터져버릴겁니다.

(테스트 해보시는 거 추천드립니다.)

그래서 우리는 

BigInteger 를 써야합니다.

Big, 보기만 해도 큰 수를 다루게 생겼습니다.

2. 1의 이유로 인한 메모리 이슈

이 문제의 경우 테스트 케이스 수(T) 가 주어집니다.

T만큼 피보나치를 구하다 보면

P가 작은 수일때는 괜찮지만

큰 수가 주어진다면

메모리의 이슈가 생기게 됩니다.

예를 들어서,

T = 10 인데

10번 다 P 가 10000이고

Q 의 값만 조금씩 바뀌는 경우라면

매번 10000의 피보나치 수를 구하는 건 너무 비효율적이고

메모리가 버티지 못하겠죠?

그리고 DP 를 사용하는 이유가

반복되는(중복되는) 연산을 없애서

메모리의 이득, 시간적 이득을 얻기 위해선데

이렇게 해서는 안되겠죠?

그래서 애초에 P의 범위가 주어져있으니까

맨처음에 피보나치를 10000까지 구해버립니다.

그 후에 

P, Q 의 값에 따른 결과값만 계산하면

메모리의 낭비가 막아지는 겁니다!!!!

이렇게만 하면 여유있게 통과하실 겁니다 ㅎㅎ

오늘도 봐주셔서 감사합니다.

문제

 

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록solution 함수를 완성하세요.

제한사항

삼각형의 높이는 1 이상 500 이하입니다.
삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

입출력 예

코드

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        int N = triangle.length;
        int M = triangle[N-1].length;
        int[][] dp = new int[N][M];

        dp[0][0] = triangle[0][0];

        for(int i = 0; i < N-1; i++){
            for(int j = 0; j < triangle[i].length; j++){
                for(int k = j; k < j+2; k++){
                    int num = dp[i][j] + triangle[i+1][k];
                    dp[i+1][k] = Math.max(dp[i+1][k], num);
                }
            }
        }

        for(int i = 0; i < M; i++){
            answer = Math.max(answer, dp[N-1][i]);
        }
        return answer;
    }
}

풀이

이 문제를 왜 DP로 풀어야 하나요?!

문제 분류가 DP 이기 때문에?

뭐 솔직히 그것도 맞긴한데

이걸 dsp로 푼다고 해봅시다.

그러면 위에서부터 쭉 내려와서 하나 계산

또 쭉 내려와서 하나 계산

이렇게 계~~~~속 할 거란 말이에요.

그러면 뭐가 문제냐!

시간 초과?

맞죠!

근데 왜 시간 초과가 나는가 하면

중복된 연산이 계속 반복 되고 있기 때문입니다.

첫번째 사진과 두번째 사진을 보면

마지막의 숫자가 하나 다른 걸로 

맨 위에서 부터 다시 내려오죠?

그렇게 중복된 연산이 반복되니까 시간이 많이 걸린다~~~~

그러면 어떻게 해야한다?

중복된 연산을 줄여야 한다.

그래서 위에서부터 내려오면서 

가장 최적의 경우를 확인하면서 내려오자 이겁니다.

저 위에꺼는 제가 처음에 풀면서

좀 복잡하게 푼 거여서

다른 소스를 봅시다.

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        int N = triangle.length;
        int M = triangle[N-1].length;
        
        for(int i = 1; i < N; i++){
            triangle[i][0] += triangle[i-1][0];
            triangle[i][i] += triangle[i-1][i-1];
            for(int j = 1; j < i; j++){
                triangle[i][j] += Math.max(triangle[i-1][j-1], triangle[i-1][j]);
            }
        }
        
        for(int i = 0; i < M; i++){
            answer = Math.max(answer, triangle[N-1][i]);
        }
        return answer;
    }
}

맨 처음, 즉 맨 위의 값은

무조건 본인이 최적이니까

그 다음칸 부터 봅시다.

내가 봐야하는건 내 왼쪽 위, 내 바로 위의 값 중 큰 값이 무엇인지 입니다.

그런데 배열의 첫번째, 맨 마지막에 위치하는 애들은 좀 달라요.

첫번째 애는 자기 바로 위의 값도 가장 첫번째 값이에요.

그러니까 왼쪽 위가 없죠?

그러니까 맨 처음값은 항상 본인의 위의 값이 최대값이 되는 겁니다.

마지막 애는 자기 위의 값이 없죠?

배열이 밑으로 갈수록 하나씩 길어지니까요.

그러니까 항상 왼쪽 위의 값이 최대값이 됩니다.

그 외에, 그러니까 맨 처음과 맨 끝 사이 애들은

이제 좀 따져봐야 합니다.

어떤 애들을?

본인의 왼쪽 위와 바로 위의 값 중 어느게 더 큰 값인지!

그래서 더 큰 값을 본인의 값과 더 하면

그 위치까지 갈 때의 최대값이 된다~~~

그렇게 해서 쭉 구하고나면

이제 마지막 줄을 보면

거기에 도달하기 위한 방법 중

가장 큰 값이 저장되어 있습니다.

그 중에서 가장 큰 값이 우리가 원하는 값이겠죠?

방법은 여러가지 있겠지만 

저는 마지막 줄을 한 번 쭉 봐서

가장 큰 값을 반환해 주었습니다.

여기까지 봐주셔서 감사합니다 ㅎㅎ