[백준] 11053번 : 가장 긴 증가하는 부분 수열 – JAVA [자바]

https://www.acmicpc.net/problem/8394

8394번: 악수

 

---

• 문제

 

---

• 문제 풀이

백준 8394번 악수는 실버 4 난이도의 DP를 이용해서 푸는 문제이다. 이 직사각형 탁자가 하나 있고 사람들 n명은 한 면에 앉아 있는다. n명이 자리를 벗어나지 않고 악수를 하는 방법의 수를 구해주면 된다.

 

예시를 보면서 이 문제를 풀어보겠다.

n = 1: 1명이 있으면 악수를 아무와도 못 하므로 방법은 1가지다.

 

n = 2: 2명이 있으면 악수를 안 하는 거 하나, 악수를 하는 거 하나, 총 2가지다. 줄은 악수를 의미한다.

 

n = 3 : 3명이 있으면 밑에 있는 사진처럼 3가지 방법으로 악수를 할 수 있다.

 

n = 4 : 4명이 있으면 밑에 있는 사진처럼 5가지 방법으로 악수를 할 수 있다.

 

n = 5 : 5명이 있으면 밑에 있는 사진처럼 8가지 방법으로 악수를 할 수 있다.

 

따라서 n = 1부터 n = 5까지의 결과를 테이블로 나타내면 패턴을 찾을 수 있다.

 

이 패턴은 피보나치 패턴과 같다. 즉, f(n) = f(n-1) + f(n-2)이다.

 

하지만, 이 문제에서는 마지막 자리만 출력하면 되기 때문에 나머지 10으로 해서 결과를 출력하면 된다.

 

dp[n] = (dp[n-1] + dp[n-2]) % 10;

 

---

• 코드

 

import java.io.*;
import java.util.*;
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[] dp = new int[10000001];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = (dp[i-1] + dp[i-2]) % 10;
        }
        System.out.print(dp[n]);
    }
}

 

---

• 후기

피보나치 패턴을 찾으면 되게 수월해지는 문제였던 거 같다. 만약에 이런 유형의 문제들을 많이 안 풀어봤으면 패턴 찾기가 힘들었을 수도 있을 거 같다.