[백준] 1463번 1로 만들기

www.acmicpc.net/problem/1463

1463번: 1로 만들기

BFS를 통해 구현했다.

처음에 1에서 n을 찾는 방식으로 구현했는데 n에서 1을 찾는 방식에 비해 메모리와 시간이 커서 고민을 많이했다.

결과론적으로 전자는 n 이상의 범위까지 탐색을 시도하지만 후자는 1로 수렴한다는 느낌인 것 같다.

(곰곰히 생각해보면 곱하기와 나누기의 차이인 것 같다.

곱셈을 통한 BFS를 하면 q에 들어가는 데이터 하나하나 사이의 값들이 커져서 채워져 있는 board의 중복을 통한 소거의 빈도가 줄어 든다.

반대로 나눗셈을 통한 BFS는 q에 들어가는 데이터 하나하나 사이의 값들이 작아져 채워져 있는 board의 중복을 통한 소거의 빈도가 늘어난다.

이는 곧 각 횟수 마다 q에 들어있는 데이터의 개수의 차이를 만들고 메모리와 시간의 차이를 만들 것이다.)

 

변수

배열 board - 10^6까지의 숫자의 방문 여부를 저장

큐 q - 매 횟수의 순서대로 큐에 저장

 

알고리즘 방식

1. q에 입력받은 n을 넣고 시작한다.

2. cur = q.front가 /1) 3으로 나누어 떨어지면, 3으로 나눈다. 2) 2로 나누어 떨어지면 2로 나눈다. 3) 1을 뺀다. /반복실행

3. 반복실행 중 cur == 1인 상황이 발생하면 board[cur] 값을 출력 후 종료

#include <iostream>
#include <queue>
using namespace std;

int board[1000001];
queue<int> q;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n;
	cin >> n;

	q.push(n);

	while (1) {
		int cur = q.front();
		q.pop();

		if (cur == 1) {
			cout << board[cur];
			return 0;
		}

		if (cur % 3 == 0 && board[cur / 3] == 0) {
			board[cur / 3] = board[cur] + 1;
			q.push(cur / 3);
		}


		if (cur % 2 == 0 && board[cur / 2] == 0) {
			board[cur / 2] = board[cur] + 1;
			q.push(cur / 2);
		}

		if (board[cur - 1] == 0) {
			board[cur - 1] = board[cur] + 1;
			q.push(cur - 1);
		}
	}
}

 

앞서 곱하기와 나누기에 대한 이해가 나중에 이 글을 다시 읽을 때도 맞다고 느꼈으면 좋겠다.