12849번: 본대 산책

가능한 경로의 수를 1,000,000,007로 나눈 나머지를 출력 한다.

www.acmicpc.net

난이도 정답률 (%) 시간 제한 (초)
Silver I 63.764 1

설계

시간 복잡도

D는 다음과 같다. (1 ≤ D ≤ 100,000)

D분 일 때, 정보 과학관에 도착해야 한다.

모든 경우를 탐색할 경우 제한 시간 내에 불가능하다. (1,000,000,007 이상이 소요되기 때문)

따라서 이전 연산 결과를 활용한 동적 계획법을 사용한다.

이 경우 시간 복잡도는 O(N) 이므로 제한 시간 1초 내에 충분하다.

 

공간 복잡도

정답은 1,000,000,007로 나눈 수 이기 때문에, 1,000,000,007 이하의 정수이다.

경우의 수를 계산할 때 이 범위를 초과할 수 있으므로 연산 과정들은 long long형으로 선언한다.

 

동적 계획법

현재 위치로 오는 경우는, 현재 위치와 연결된 위치들의 이전에 방문한 횟수들을 더한 값이다.

따라서 일반식은 다음과 같이 설정할 수 있다.

// a, b는 i와 연결되어 있는 위치
dp[n][i] = dp[n-1][a] + dp[n-1][b] ...

dp를 다음과 같이 설정한다.

dp[n][index]  // n초 후 해당 건물 위치 index로 가는 경우의 수

여기서 n이 매우 크고, n을 계산할 때는 n-1번째 값만 필요하므로 dp 배열을 1차원으로 설정한다.

여기서 정보과학관에서 출발해야 하는데, index를 다음과 같이 설정한다.

  • 0 : 정보과학관
  • 1 : 전산관
  • 2 : 신앙관
  • 3 : 미래관
  • 4 : 진리관
  • 5 : 환경직기념관
  • 6 : 학생회관
  • 7 : 형남공학관

정보 과학관에서 출발하므로 dp의 0번째는 = 1이 된다.

dp[8] = {1, 0, 0, 0, 0, 0, 0, 0}; // n = 0 일 때

탐색을 진행하면서 dp의 값들을 이전 값들을 이용해 갱신한다.

이 때 이동할 수 있는 위치는 정해져 있으므로 연결된 점들을 이용한다.

dp[0] = 1;
while (D--) {
  long long temp[8] = {
      0,
  };

  for (int i = 0; i < 8; i++) {
    temp[0] = dp[1] + dp[3];
    temp[1] = dp[0] + dp[2] + dp[3];
    temp[2] = dp[1] + dp[3] + dp[4] + dp[5];
    temp[3] = dp[0] + dp[1] + dp[2] + dp[5];
    temp[4] = dp[2] + dp[5] + dp[6];
    temp[5] = dp[3] + dp[2] + dp[4] + dp[7];
    temp[6] = dp[4] + dp[7];
    temp[7] = dp[5] + dp[6];
  }

  for (int i = 0; i < 8; i++) {
    dp[i] = temp[i] % 1000000007;
  }
}

 

테스트케이스

종류 input output
예제 10 9857

 

코드

 

changicho/algorithm-training

The repository of problem solving (especially algorithm problems of computer science) - changicho/algorithm-training

github.com

 

정리

내 코드 (ms) 빠른 코드 (ms)
0 0

 

+ Recent posts