최고의 개발자 (목표)

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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

        int n = Integer.parseInt(br.readLine());
        String[] st = br.readLine().split(" ");

        int[] dp = new int[n];

        dp[0] = Integer.parseInt(st[0]); 
        int max = dp[0];

        for(int i = 1; i < n; i++){
            dp[i] = Math.max(dp[i-1]+Integer.parseInt(st[i]), Integer.parseInt(st[i]));
            max = max < dp[i] ? dp[i] : max;
        }

        System.out.println(max);

    }
}

풀이

dp[i]는 i번째 정수까지 있을 때의 구할 수 있는 합 중 가장 큰 합이다.

st는 입력받은 배열이다.

이때 정수 n이 최소 1개이므로 dp[0]에는 st[0]을 미리 넣고, 가장 큰 합을 저장하는 변수인 max에도 st[0]을 넣어놓는다.

dp[i]는 i-1번째 정수까지 있을 때의 구할 수 있는 최대 합에 st[i]를 더한 것이 될 수도 있고, 아니면 현재 들어온 st[i] 자체가 될 수도 있다. 따라서 두 수를 비교해 더 큰 수를 dp[i]에 저장하고, max 값도 비교해서 바꿔준다.

문제

Mahima has been experimenting with a new style of art. She stands in front of a canvas and, using her brush, flicks drops of paint onto the canvas. When she thinks she has created a masterpiece, she uses her 3D printer to print a frame to surround the canvas.

Your job is to help Mahima by determining the coordinates of the smallest possible rectangular frame such that each drop of paint lies inside the frame. Points on the frame are not considered inside the frame.

입력

The first line of input contains the number of drops of paint, N, where 2 ≤ N ≤ 100 and N is an integer. Each of the next N lines contain exactly two positive integers X and Y separated by one comma (no spaces). Each of these pairs of integers represents the coordinates of a drop of paint on the canvas. Assume that X < 100 and Y < 100, and that there will be at least two distinct points. The coordinates (0, 0) represent the bottom-left corner of the canvas.

출력

Output two lines. Each line must contain exactly two non-negative integers separated by a single comma (no spaces). The first line represents the coordinates of the bottom-left corner of the rectangular frame. The second line represents the coordinates of the top-right corner of the rectangular frame.

코드

import sys

if __name__ == '__main__':
    N = int(sys.stdin.readline().rstrip())

    x_coordinates = []
    y_coordinates = []

    for i in range(N):
        x,y = map(int, sys.stdin.readline().rstrip().split(","))
        x_coordinates.append(x)
        y_coordinates.append(y)
    
    print(min(x_coordinates)-1,min(y_coordinates)-1, sep=",")
    print(max(x_coordinates)+1,max(y_coordinates)+1, sep=",")

풀이

각 점을 포함하는 프레임의 왼쪽 아래와 오른쪽 위 좌표를 구하는 것이므로, 왼쪽 아래와 오른쪽 위 프레임의 위치가 어디가 될지 생각해보면 된다. 프레임의 왼쪽 아래의 x, y 좌표는 분포하는 점 중에서 가장 작은 x와 가장 작은 y와 같을 것이다. 이때, 프레임이 점 밖에 있어야 하기 때문에, (가장 작은 x-1, 가장 작은 y-1)이 왼쪽 아래의 좌표가 된다.

오른쪽 위는 위가 같은 방법으로 (가장 큰 x+1, 가장 작은 y+1) 가 될 것이다.

문제

Now that Snapchat and Slingshot are soooo 2018, the teenagers of the world have all switched to the new hot app called BAPC (Bidirectional and Private Communication). This app has some stricter social rules than previous iterations. For example, if someone says goodbye using Later!, the other person is expected to reply with Alligator!. You can not keep track of all these social conventions and decide to automate any necessary responses, starting with the most important one: the greetings. When your conversational partner opens with he...ey, you have to respond with hee...eey as well, but using twice as many e’s!

Given a string of the form he...ey of length at most 1000, print the greeting you will respond with, containing twice as many e’s.

입력

• The input consists of one line containing a single string s as specified, of length at least 3 and at most 1000.

출력

Output the required response.

코드

import java.util.Scanner;

public class 백준_17548 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String st = sc.next();

        int eCount = 0;
        
        for(int i = 0; i < st.length(); i++){
            char c = st.charAt(i);
            if(c == 'e'){
                eCount += 1;
            }
        }
        System.out.print("h");
        for(int i = 0; i < eCount*2; i++){
            System.out.print("e");
        }
        System.out.print("y");
    }
}

풀이

문제를 해석해보면 입력 String의 e를 2배로 출력하면 된다. 최소 입력은 'hey'이다.

입력받은 String에서 e의 개수를 세서 eCount 변수에 저장했다. 

출력은 h, e, y를 따로 출력해 e를 중간에 여러 개 출력할 수 있도록 했다.

문제

두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있으며, 최소 공배수는 30이다.

두 자연수 A와 B가 주어졌을 때, A와 B의 최소공배수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 둘째 줄부터 T개의 줄에 걸쳐서 A와 B가 주어진다. (1 ≤ A, B ≤ 45,000)

출력

첫째 줄부터 T개의 줄에 A와 B의 최소공배수를 입력받은 순서대로 한 줄에 하나씩 출력한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        /* 유클리드 호제법
        1. a와 b의 최대공약수
        == b와 r의 최대공약수
        == r과 r2의 최대공약수
        ...
        a % b => r
        b % r => r2
        r % r2 => r3
        if) r3가 0, 즉 나머지가 0이면 최대공약수는 r2

        2. a와 b의 최대공배수
        -> a*b / gcd(a,b)
        */

        int T = Integer.parseInt(st.nextToken());

        for(int i = 0; i < T; i++){
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());

            int r = gcd(A, B);
            System.out.println(A*B/r);

        }
    }

    public static int gcd(int a, int b){
        while(b!=0){
            int r = a % b;
            a = b;
            b = r;
        }
        return a;
    }
}

풀이

이 문제는 시간제한이 1초이기 때문에 유클리드 호제법을 써야 한다.

유클리드 호제법을 이용해 최대공약수를 구하고, A * B / 최대공약수를 해서 최소공배수를 구했다.

유클리드 호제법은 https://chelim.tistory.com/49 에 따로 설명을 올렸다.

문제

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.

예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총점수는 10 + 20 + 25 + 20 = 75점이 된다.

계단 오르는 데는 다음과 같은 규칙이 있다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

입력

입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300 이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000 이하의 자연수이다.

출력

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

코드

import java.io.*;

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

        int N = Integer.parseInt(br.readLine());
        int[] stairs = new int[N+2];
        int[] dp = new int[N+2]; // 계단 1칸이면 밑에 0,1,2 값에서 outofindex

        for(int i = 0; i < N; i++){
            stairs[i] = Integer.parseInt(br.readLine());
        }

        // dp[0] 즉 한 칸 이동에서의 최대는 자기 자신
        dp[0] = stairs[0];
        // dp[1] 은 자기자신과 전칸+자기자신 중 최대
        dp[1] = Math.max(stairs[0]+stairs[1], stairs[1]);
        // dp[2] 는 st[0]+st[2] 또는 st[1]+st[2] 중 최대
        dp[2] =  Math.max(stairs[0]+stairs[2], stairs[1]+stairs[2]);

        for(int i = 3; i < N; i++){
            dp[i] = Math.max(dp[i-3] + stairs[i-1] + stairs[i], dp[i-2] + stairs[i]);
        }
        System.out.println(dp[N-1]);
    }   
}

풀이

문제의 조건을 보고 dp 식을 세워야 한다. 마지막 계단은 무조건 밟아야 한다는 것과, 1칸이나 2칸 이동이 가능하지만 1칸 이동을 연속으로 3번은 불가능하다는 것이다. 즉 1번 계단->2번 계단으로 이동했다면 2번 계단에서는 무조건 4번 계단으로 가는 선택지 밖에 존재하지 않는다.

일단 마지막 계단을 무조건 밟아야 한다는 조건을 생각해보자. 마지막 계단을 n번째 계단이라고 가정하면, n-1번째 계단을 밟고 마지막 계단을 밟는 것과 n-2번째 계단을 밟고 마지막 계단을 밟는 경우가 존재한다. 

이때, n-1번째 계단에서 n번째 계단으로 가는 경우는 더 생각해봐야 하는 것이 있다. n-2번째 -> n-1번째 -> n번째는 조건에 어긋나기 때문에 n-1번째 -> n번째로 가기 위해서는 무조건 n-3번째 -> n-1번째 -> n번째가 되어야한다. 따라서

아래 그림과 같이 최종적으로 2가지 방법을 비교해 총 점수가 더 큰 계단으로 이동해야 한다.

이를 식으로 바꾸면, 왼쪽의 경우는 dp[n-3] + stairs[n-1] + stairs[n] 이 되고, 오른쪽의 경우는 dp[n-2] + stairs[n] 이 된다.

따라서, dp[n] = max(dp[n-3] + stairs[n-1] + stairs[n], dp[n-2] + stairs[n]) 로 구할 수 있다.

dp[0], dp[1], dp[2]는 조건식이 달라서 for문에 들어가기전에 따로 값을 넣어줬고, 계단이 1칸일 때 dp[1], dp[2]에 값을 넣어주는 라인에서 ArrayOutOfIndex 에러가 나기 때문에 dp와 stairs의 크기를 N+2로 지정했다.

문제

지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다.

어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다.

그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다. 예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다. (01, 10은 만들 수 없게 되었다.) 또한 N=4일 때는 0011, 0000, 1001, 1100, 1111 등 총 5개의 2진 수열을 만들 수 있다.

우리의 목표는 N이 주어졌을 때 지원이가 만들 수 있는 모든 가짓수를 세는 것이다. 단 타일들은 무한히 많은 것으로 가정하자.

입력

첫 번째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 1,000,000)

출력

첫 번째 줄에 지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다.

코드

import sys

if __name__ == '__main__':
    N = int(sys.stdin.readline().rstrip())

    dp = [0] * 1000001
    dp[1] = 1
    dp[2] = 2

    for i in range(3,N+1):
        dp[i] = (dp[i-1] + dp[i-2]) % 15746
    
    print(dp[N])

풀이

N이 1일 때는 가능한 2진 수열이 1로 총 1개이다.

N이 2일 때는 가능한 2진 수열이 11, 00으로 총 2개이다.

N이 3일 때는 가능한 2진 수열이 111, 100, 001로 총 3개이다.

N이 4일 때는 가능한 2진 수열이 1111, 1100, 1001, 0011, 0000으로 총 5개이다.

N이 5일 때는 가능한 2진 수열이 11111, 11100, 11001, 10011, 00111, 10000, 00100, 00001로 총 8개이다.

이를 보면 증가하는 추세가 피보나치 수의 수열과 같다는 것을 알 수 있다.

즉 dp[i] = dp[i-2] + dp[i-1] 임을 알 수 있다.

헷갈리지 않기 위해서 dp[i]의 값을 N이 i일 때 가능한 2진 수열의 길이 % 15746로 정하였다. 즉 index가 0일 때는 사용하지 않았다.

문제

KOI 전자에서는 건강에 좋고 맛있는 훈제오리구이 요리를 간편하게 만드는 인공지능 오븐을 개발하려고 한다. 인공지능 오븐을 사용하는 방법은 적당한 양의 오리 훈제 재료를 인공지능 오븐에 넣으면 된다. 그러면 인공지능 오븐은 오븐구이가 끝나는 시간을 분 단위로 자동적으로 계산한다.

또한, KOI 전자의 인공지능 오븐 앞면에는 사용자에게 훈제오리구이 요리가 끝나는 시각을 알려 주는 디지털 시계가 있다. 

훈제오리구이를 시작하는 시각과 오븐구이를 하는 데 필요한 시간이 분단위로 주어졌을 때, 오븐구이가 끝나는 시각을 계산하는 프로그램을 작성하시오.

입력

첫째 줄에는 현재 시각이 나온다. 현재 시각은 시 A (0 ≤ A ≤ 23) 와 분 B (0 ≤ B ≤ 59)가 정수로 빈칸을 사이에 두고 순서대로 주어진다. 두 번째 줄에는 요리하는 데 필요한 시간 C (0 ≤ C ≤ 1,000)가 분 단위로 주어진다. 

출력

첫째 줄에 종료되는 시각의 시와 분을 공백을 사이에 두고 출력한다. (단, 시는 0부터 23까지의 정수, 분은 0부터 59까지의 정수이다. 디지털 시계는 23시 59분에서 1분이 지나면 0시 0분이 된다.)

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(br.readLine());

        B = B + C;
        
        while(B >= 60){
            A += 1;
            B -= 60;
        }

        while(A >= 24){
            A -= 24;
        }
        
        System.out.printf("%d %d", A, B);
    }
}

풀이

현재 시각에 요리하는데 필요한 시간을 더하면 되는 문제이다. 고려해야할 부분은 A시 B분일 때, A시는 최대 23이고 B는 최대 59라는 것이다. 요리하는데 필요한 시간인 C가 분단위로 주어지기 때문에 B에 C를 더해주고 B가 60이 넘지 않을 때까지 A에 1을 더하고 B에 60씩 빼준다. 즉 B분이 60보다 작아질 때까지 60분을 1시간으로 고치는 것이다.

A시도 최대 23까지 가능하기 때문에 A가 24보다 작아질 때까지 24를 빼준다.

문제

나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다.

재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다.

재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다.

재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알고 싶어 한다. 재민이를 도와주자!

입력

첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000)

이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경우 해당 수를 쓴다.

정수가 "0"일 경우에 지울 수 있는 수가 있음을 보장할 수 있다.

출력

재민이가 최종적으로 적어 낸 수의 합을 출력한다. 최종적으로 적어낸 수의 합은 231-1보다 작거나 같은 정수이다.

코드

import sys

if __name__ == '__main__':
    K = int(sys.stdin.readline().rstrip())
    stack = []

    for i in range(K):
        num = int(sys.stdin.readline().rstrip())
        if(num == 0):
            stack.pop()
        else:
            stack.append(num)
    print(sum(stack))

풀이

정수가 0일 때 가장 최근에 쓴 수를 지우려면 stack 개념이 필요하다. python에서는 스택을 list로 구현한다. 0인 경우에 스택에서 pop을 해주고 0이 아닌 경우에는 stack에 넣어준다.

문제

정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 다섯 가지이다.

• push X: 정수 X를 스택에 넣는 연산이다.
• pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 스택에 들어있는 정수의 개수를 출력한다.
• empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
• top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야 하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Stack<String> stack = new Stack<>();
        int N = Integer.parseInt(br.readLine());

        for(int i = 0; i < N; i++){
            String[] st = br.readLine().split(" ");
            if(st[0].equals("push")){
                stack.push(st[1]);
            }else if(st[0].equals("pop")){
                if(stack.isEmpty()){
                    System.out.println("-1");
                }else{
                    System.out.println(stack.pop());
                }
            }else if(st[0].equals("size")){
                System.out.println(stack.size());
            }else if(st[0].equals("empty")){
                if(stack.isEmpty()){
                    System.out.println(1);
                }else{
                    System.out.println(0);
                }
            }else if(st[0].equals("top")){
                if(stack.isEmpty()){
                    System.out.println("-1");
                }else{
                    System.out.println(stack.peek());
                }
            }
        }
    }
}

풀이

스택에 대해 간단히 설명하면 바닥이 막힌 바구니에 쌓는 것이라고 생각하면 된다. 바구니에 상자를 넣는다면, 제일 처음 넣은 상자가 아래에 깔리게 된다. 그리고 상자를 바구니에서 빼려면 제일 위에 있는 상자가 먼저 빠지게 되는 구조이다.

push 경우에는 뒤에 스택에 넣을 숫자가 오기 때문에 realine()으로 한 줄을 입력받고 split으로 배열에 저장해주었다. push라면 배열에 [push, 숫자] 이렇게 저장이 될 것이고, size 같은 것은 [size] 이렇게 저장이 될 것이다.

push x는 x를 스택에 넣어야 하기 때문에 실제 스택에 있는 함수인 push 함수를 이용했다.

pop은 스택에 아무것도 없으면 -1을 출력하고, 수가 존재하면 제일 위의 정수를 스택에서 제거하면서 출력해야 한다. 따라서 스택의 isEmpty() 함수로 스택이 비어있는지 확인하고 비어있다면 -1을 출력한다. 스택이 비어있지 않다면 pop() 함수를 이용해 스택에서 제일 위에 있는 수를 스택에서 제거하면서 출력한다.

size는 스택에 있는 size() 함수를 이용했고, empty의 경우 isEmpty()를 이용했다.

top의 경우 pop의 의미와 비슷하지만 스택에서 제거는 하면 안되고 출력만 해야 하기 때문에 peek()을 이용해 제일 위에 있는 수를 출력했다.

문제

오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.

파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.

N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100)

출력

각 테스트 케이스마다 P(N)을 출력한다.

코드

import sys

if __name__ == '__main__':
    list = [1,1,1]

    T = int(sys.stdin.readline().rstrip())
    pn = []
    for i in range(T):
        pn.append(int(sys.stdin.readline().rstrip()))
    
    maximum = max(pn)

    for i in range(3, maximum):
        list.append(list[i-2] + list[i-3])
  
    for i in range(T):
        print(list[pn[i]-1])

풀이

10개의 P(N)이 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 라는 것을 주목하면, 뭔가 피보나치와 닮아있다는 것을 느낄 수 있을 것이다. 첫 번째 수 + 두 번째 수 = 2, 두 번째 수 + 세 번째 수 = 2, 세 번째 수 + 네 번째 수 = 3 이걸 나열하면 223이다. 즉 예시에 있는 것과 겹치는 부분이 있다는 것을 확인할 수 있다. 세 번째 수와 네 번째 수를 더해서 여섯 번째 수가 나온 것을 보면, 현재 수는 앞 앞 번째 수와 앞 앞 앞 번째 수를 더한 것임을 알 수 있다.

N을 입력 받을 때마다 첫 번째부터 원하는 N번째까지 P(N)을 계속 구하면 시간이 오래 걸릴 것 같아서 입력받은 N 중에서 최댓값을 알아내고, 그 최댓값까지 P(N)을 구해놓았다. 그 후 입력받은 N에 따른 P(N)을 출력했다.