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

 

'공부 > 알고리즘 문제풀이' 카테고리의 다른 글

백준.12849.본대 산책  (0) 2021.01.26
백준.12852.1로 만들기 2  (0) 2021.01.25
백준.1197.최소 스패닝 트리  (0) 2021.01.24
큰 수 연산 (Big Integer)  (0) 2021.01.04
삼성 7699. 수지의 수지 맞는 여행  (0) 2019.12.31
삼성 9088. 다이아몬드  (0) 2019.12.27
 

12852번: 1로 만들기 2

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다.

www.acmicpc.net

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

 

설계

시간 복잡도

X는 최대 10^6인 자연수이다.

 

X부터 1까지 탐색을 진행할 때 다음 두가지 방법을 이용할 수 있다.

  • BFS
  • 동적 계획법

BFS의 경우 최악의 경우 시간 복잡도는 O(N) 이하이다.

동적 계획법의 경우 최악의 경우 시간 복잡도는 O(N) 이다.

두 방법 모두 제한시간 0.5초 내에 충분하다.

 

공간 복잡도

X는 최대 10^6인 자연수이다.

 

저장해야 되는 정보는 다음과 같다.

 

  • 현재 노드 (index)
  • 부모 노드
  • 1까지 도달하는데 거치는 노드의 수

이 값 모두 int형으로 충분하다.

 

테스트케이스

종류 input output
예제 1 2 1
2 1
예제 2 10 3
10 9 3 1
임계값 (최소) 1 0
1
임계값 (최대) 1000000 19
1000000 500000 250000 125000 62500 31250 15625 15624 7812 3906 1953 651 217 216 108 54 27 9 3 1 

 

풀이

BFS

 

changicho/algorithm-training

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

github.com

BFS를 이용해 X에서 1까지 탐색할 수 있다.

 

이 때 저장해야 할 정보는 다음과 같다.

  • 현재까지 거쳐온 노드의 정보

노드의 정보에서 가장 마지막에 저장되어있는 것이 현재 방문한 노드이므로 vector로만 나타낼 수 있다.

이 때 이전에 방문한 정점을 다시 방문하지 않도록 주의한다.

struct Status {
  vector<int> history;
};

queue<Status> q;
vector<int> answer;
q.push({{N}});

while (!q.empty()) {
  Status cur = q.front();
  q.pop();

  int node = cur.history.back();
  if (node == 1) {
    answer = cur.history;
    break;
  }
  if (visited[node]) continue;
  visited[node] = true;

  vector<int> new_history = cur.history;

  if (node % 3 == 0) {
    new_history.push_back(node / 3);
    q.push({new_history});
    new_history.pop_back();
  }
  if (node % 2 == 0) {
    new_history.push_back(node / 2);
    q.push({new_history});
    new_history.pop_back();
  }
  if (node - 1 > 0) {
    new_history.push_back(node - 1);
    q.push({new_history});
    new_history.pop_back();
  }
}

 

동적 계획법

 

changicho/algorithm-training

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

github.com

동적 계획법을 이용하고, 각 상황별로 어느 노드에서 현재 노드로 왔는지를 기록한다.

이 떄의 시간 복잡도는 O(N)이다.

 

다음 자료구조에서 나타내는 정보는 다음과 같다.

  • 현재 노드 (index)
  • 부모 노드
  • 1까지 도달하는데 거치는 노드의 수
struct Edge {
  int length; // 1까지 도달하는데 거치는 노드의 수
  int from;   // 부모 노드
};
Edge dp[1000001]; // 현재 노드 index

일반 식은 다음과 같다.

dp[i] = min({dp[i - 1].length + 1, i - 1}, {dp[i / 2].length + 1, i / 2}, {dp[i / 3].length + 1, i / 3})

현재 index에서의 dp값은 현재 index로 도달할 수 있는 3가지 경우 중에서 가장 length가 짧은 경우이다.

 

초기 값은 다음과 같다.

dp[1] = {0, 0};

이 방법으로 bottom-up 방식으로 풀이한다.

 

X가 1인 경우는 보장되므로 2부터 탐색을 진행한다.

 

이 때 i번째를 구할 때 i-1번쨰를 이용해 먼저 구해 초기값을 할당하지 않도록 구성한다.

for (int i = 2; i <= N; i++) {
  dp[i] = {dp[i - 1].length + 1, i - 1};
  if (i % 2 == 0 && dp[i].length > dp[i / 2].length + 1) {
    dp[i] = {dp[i / 2].length + 1, i / 2};
  }
  if (i % 3 == 0 && dp[i].length > dp[i / 3].length + 1) {
    dp[i] = {dp[i / 3].length + 1, i / 3};
  }
}

 

정리

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

 

'공부 > 알고리즘 문제풀이' 카테고리의 다른 글

백준.12849.본대 산책  (0) 2021.01.26
백준.12852.1로 만들기 2  (0) 2021.01.25
백준.1197.최소 스패닝 트리  (0) 2021.01.24
큰 수 연산 (Big Integer)  (0) 2021.01.04
삼성 7699. 수지의 수지 맞는 여행  (0) 2019.12.31
삼성 9088. 다이아몬드  (0) 2019.12.27

+ Recent posts