https://www.acmicpc.net/problem/25418
입력으로 양의 정수 A와 K가 주어지면, 아래 연산을 이용하여 A를 K로 변경하려고 한다. 정수 A를 변경할 때 사용할 수 있는 연산 종류는 아래와 같다.
- 연산 1: 정수 A에 1을 더한다.
- 연산 2: 정수 A에 2를 곱한다.
정수 A를 정수 K로 만들기 위해 필요한 최소 연산 횟수를 구하는 문제다.
문제 탐색하기
- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정
ex. 가능한 시간 복잡도, 알고리즘 선택
입출력 제한
- 1 ≤ A < K ≤ 1,000,000
1697 - 숨바꼭질과 비슷한 문제다. 최소 방문 횟수를 저장할 방문 배열을 만들어 놓고 적당히 큰 값으로 초기화한다. 이후 A에서 K에 도달하기까지 너비 우선 탐색을 돌려야 한다. K까지만 탐색을 하더라도 {x+1, x*2} 두 가지 값을 모두 queue에 넣으면서 진행하면 시간초과가 날 수 있다. 중복도 줄이기 위해 최소가 될 가능성이 없는 좌표는 queue에 넣지 않는 방식으로 탐색을 진행해야 한다.
코드 설계하기
위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!
- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지
- A, K 입력받기
- 방문 배열을 1,000,000,000 값으로 초기화하고 너비 우선 탐색 함수 돌리기
- queue에 다음 좌표(현재 값에서 1을 더한 좌표나 2를 곱한 좌표)를 조건에 따라 넣으면서 방문 배열 값 갱신하기
- 조건: 다음 좌표가 K를 넘지 않고, 방문 배열의 다음 좌표에 해당하는 값을 더 작게 갱신할 수 있는 경우
- 방문 배열의 K 좌표에 해당하는 값을 출력하기
시도 회차 수정 사항 (Optional)
- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!
pass
정답 코드
#include <iostream>
#include <queue>
using namespace std;
int a,k,visit[1000001];
void bfs() {
queue<int> q;
q.push(a);
visit[a] = 0;
while (!q.empty()) {
int cur = q.front();
q.pop();
int nums[2] = {cur+1,cur*2};
for (int i=0; i<2; i++) {
if (nums[i]<=k && visit[nums[i]]>visit[cur]+1) {
visit[nums[i]] = visit[cur]+1;
q.push(nums[i]);
}
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> a >> k;
fill(visit,visit+k+1,1e9);
bfs();
cout << visit[k];
}