[백준] 8394 악수 - Java

 

 

 

문제 출저

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

8394번: 악수

 

 

 

문제 풀이

일렬로 n명의 사람이 있습니다. 양 옆에 있는 사람 중 한 사람만 악수가 가능합니다. 악수를 하는 총 방법의 수를 구해야 합니다. 

 

 

사람의 수가 n으로 주어지는데 범위가 10,000,000 입니다. 큰 크기에 dp로 문제를 풀 생각을 했고 점화식을 찾았습니다.

사람이 추가될 때 경우의 수는 2개 입니다. 악수를 하거나 악수를 안하거나 2개입니다. 악수를 하지 않은 경우의 수는 옆에 사람이 악수를 한 상태, 악수를 안한 상태 모두 가능합니다. 악수를 한 경우의 수는 옆에 사람이 악수를 안하고 있는 상태여야 합니다. 편의상 옆에 사람과 악수는 왼쪽으로 했습니다. 

 

dp[i][0] = dp[i-1][0] + dp[i-1][1]

dp[i][1] = dp[i-1][0] 

 

이런 점화식이 나옵니다. 정답은 dp[n][0] + dp[n][1] 입니다. 

하지만 2차원 int 배열로 하면 메모리 초과가 발생합니다. 

그러므로 일정 변수를 선언해서 변수의 값을 계속 업데이트 하는 식으로 코드를 바꿔 문제를 풀었습니다.

 

 

 

소스 코드

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

/*
악수
https://www.acmicpc.net/problem/8394

n = 10_000_000
DP로 풀자

악수를 한 경우, 악수를 안 한 경우
2가지 경우로 나눠서 점화식을 세운다.

악수를 할려면 왼쪽 사람이 악수를 안 해야 한다.
악수를 안한 경우는 왼쪽 사람이 악수를 하든 안하든 상관이 없다.

메모리 초과
DP int 2차원 배열을 사용하면 메모리 초과가 발생한다.

 */
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 zero = 1;
    int one = 0;

    int newZero = 0;
    int newOne = 0;
    for(int i = 1; i < n; i++) {
      newZero = (zero + one) % 10;
      newOne = zero % 10;

      zero = newZero;
      one = newOne;
    }

    int answer = (zero + one) % 10;

    System.out.println(answer);

  }

}