[자바] 백준 8394 - 악수 (java)

 문제 : boj8394

---

 

필요 알고리즘 개념

•  동적계획법 (다이나믹 프로그래밍, DP, dynamic programming)
  • 동적계획법을 안다면 어렵지 않게 풀 수 있다. 동적계획법을 몇 개 풀어봤었다면 풀이를 몇초만에 떠올릴 수 있는 정도로 응용없이 기본적인 형태의 문제이다. 참고로 방법의 수, 경우의 수를 구하는 문제들은 높은 확률로 동적계획법을 사용해 풀리는 경우가 많다.
• 나머지 연산 (모듈러, modular)
  • 수가 매우 커지므로, 자바의 BigInteger(큰 수 표현 가능. 대신 느림)를 쓰거나, 나머지 연산을 사용해줘야 한다(안해보긴 했는데 BigInteger 사용하면 메모리초과날 것 같긴하다). '%'를 사용하는 나머지 연산을 알고 있어야 더 쉽게 통과 가능하다. 

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  우선 생각해봐야 하는게, 문제를 약간 축소시켜보자. 어차피 가장 좌측 인원은 자신의 왼쪽 사람이 없으므로 악수할수 없다. 가장 우측 인원또한 오른쪽 사람과 악수할 수 없다. 그 둘의 차이일 뿐, 애초에 왼쪽, 오른쪽을 나누는게 의미가 없다. 그럼 방향을 왼쪽 사람과만 악수하는 것으로 고정해도 문제될게 전혀 없다. 예를들어 3번이 자신의 왼쪽인 2번과 악수를 하는건 2번 입장에서 오른쪽과 악수하는 것으로 동일하다.

 

  방향을 고정시키고 생각해보면 각 사람마다 경우의 수는 '1.왼쪽 사람과 악수를 안한다 / 2. 왼쪽 사람과 악수를 한다.'의 두가지이다. 그럼 모든 경우를 직접 구해보려 한다면 O(2^n)이 필요하고, n이 최대 1000만이므로 절대 불가능하다. 이 때 둘의 주의점은 왼쪽 사람과 악수를 하는 경우라면, 그 왼쪽 사람은 악수를 안하고 있어야 한다.

 

  그럼 점화식을 한번 만들어보자. dp[i][0]을 i번 인덱스 사람이 자신의 왼쪽 사람과 악수를 안할때의 방법의 수, dp[i][1]을 i번 인덱스 사람이 자신의 왼쪽 사람과 악수를 할 때의 방법의 수라고 하자.

 

  간단하게 위와 같이 점화식이 세워진다. dp[i][1]을 말로 설명해보면, i번 사람이 자신의 왼쪽과 악수를 할때의 방법의 수는 자신의 왼쪽사람(i-1번)이 악수를 하지 않는 방법의 수와 동일하다. dp[i][0]은 i번 사람이 자신의 왼쪽과 악수를 안하니 자신의 왼쪽사람이 뭘 하고 있던 상관이 없다. 따라서 자신의 왼쪽 사람이 악수를 할 때의 방법의수 + 악수를 안할 때의 방법의수가 된다.

 

   그리고 '마지막 자리만 출력' 이라고 했으므로 매번 결과값의 마지막 자리만 남겨주면 된다(%10을 해주면 된다). 어차피 덧셈에서 마지막 자리수에 영향을 끼치는건 마지막 자리수 뿐이다. 즉, 12345 + 128312312748의 마지막 자리만 알려고 한다면 둘의 마지막 자리수만 더해보면 알 수 있다.

 

  최종적으로 정답은 dp[n-1][0] + dp[n-1][1]이 된다. 즉 마지막 사람이 (0번 인덱스부터 시작하므로 n-1번이 마지막 사람이다.) 악수를 할 때의 경우의수 + 악수를 안할 때의 경우의수가 된다. 이 때 주의점은 마지막에 둘을 더한 값이 10을 넘어갈 수 있으므로 마찬가지로 마지막 자리만 남겨서 출력해줘야 한다. 내 경우 이거때문에 2번이나 틀렸다 ㅠ

 

---

 

코드 : github

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

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] dp = new int[n][2];
        dp[0][0] = 1;
        for (int i = 1; i < n; i++) {
            dp[i][1] = dp[i-1][0];
            dp[i][0] = dp[i-1][0] + dp[i-1][1];
            dp[i][1] %= 10;
            dp[i][0] %= 10;
        }
        System.out.println((dp[n-1][0] + dp[n-1][1])%10);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}