boj - 9095 1, 2, 3 더하기 [java]

vetto·2022년 10월 3일
0

Boj

목록 보기
10/18
post-thumbnail

2022-10-03 algorithm

boj_9095 1, 2, 3 더하기 - silver 3

Link : 1, 2, 3 더하기

정보

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

  • 1+1+1+1
  • 1+1+2
  • 1+2+1
  • 2+1+1
  • 2+2
  • 1+3
  • 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

예제 입력1

예제 출력1

풀이

  1. 11길이에 배열을 만든다.(계산을 편하게 하기 위함)
  2. 1,2,3을 만들때 방법의 수를 계산해서 넣어준다.
  3. 그 후 i인덱스 배열에 i-1번째 + i-2번째 + i-3번째를 더해서 넣어준다.

코드

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[] dp = new int[11];
        
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        
        for (int i = 4; i < 11; i++) {
            dp[i] = dp[i-3]+dp[i-2]+dp[i-1];
        }
        
        int t = Integer.parseInt(br.readLine());
        
        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());
            System.out.println(dp[n]);
        }
    }
}

결과

tags: algorithm, Boj, dp
profile
좋은 개발자가 되고 싶은 사람

0개의 댓글