Baekjun, 9095, 1, 2, 3 plus (with. Java)

This is an article about Baekjun 9095, 1, 2, 3 plus (with.Java).

I want to solve the coding test problem, find out how to solve it differently from the retrospective of the problem I solved, and get to know.

Let’s get to the problem first.

Problem

There are a total of 7 methods of expressing integer 4 as the sum of 1, 2, and 3.

You must use at least one number when representing the sum.

1+1+1+1

1+1+2

1+2+1

2+1+1

2+2

1+3

3+1

Write a program to find the number of ways to express n as the sum of 1, 2, and 3, given the integer n.

Input

The number of test cases T is given in the first line.

Each test case consists of a line, given an integer n. N is positive and is less than 11.

Output

For each test case, output the number of methods to express n as the sum of 1, 2, and 3.

problem solving

import java.io.*;

public class Main {

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

		for (int t = 0; t < T; t++) {
			int n = Integer.parseInt(br.readLine());
			int[] dp = new int[11];

			dp[1] = 1;
			dp[2] = 2;
			dp[3] = 4;

			for (int i = 4; i <= n; i++) {
				dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
			}

			bw.write(dp[n] + "\n");
		}
		bw.flush();
	}
}

Solution Description

This code is a program that utilizes dynamic programming to calculate the number of methods for expressing integer num as the sum of 1, 2, and 3.

I’ll explain it with examples to make it easier to understand mathematically.

• Every time you make a number i
  • (if you make i-1 and add 1)
  • (If you make i-2 and add two)
  • (if you make i-3 and add 3)
• Since these three methods do not overlap each other, the total number of cases is
  [ dp[i] = dp[i-1] + dp[i-2] + dp[i-3] ] It can be defined as .

It should now be understood that it does not mean (i-1) + (i-2) + (i-3) = i, but that it is an igniting representation of all cases in which **i can be made.