문제 설명
자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다.
- x에 n을 더합니다
- x에 2를 곱합니다.
- x에 3을 곱합니다.
자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때 x를 y로 만들 수 없다면 -1을 return 해주세요.
제한사항
- 1 ≤ x ≤ y ≤ 1,000,000
- 1 ≤ n < y
BFS를 활용하여 간단하게 풀 수 있는 문제이다.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <string> | |
#include <vector> | |
#include <queue> | |
using namespace std; | |
typedef pair<int,int> point; | |
bool vis[1000001]; | |
queue <point> q; | |
int solution(int x, int y, int n) { | |
int answer = 0; | |
if(x == y) return 0; | |
q.push(make_pair(x,0)); | |
while(!q.empty()){ | |
int cur = q.front().first; | |
int curt = q.front().second; | |
q.pop(); | |
if(cur + n <= y && !vis[cur + n]){ | |
vis[cur + n] = true; | |
if(cur + n == y) | |
return curt + 1; | |
q.push(make_pair(cur + n ,curt + 1)); | |
} | |
if(cur * 2 <= y && !vis[cur * 2]){ | |
vis[cur * 2] = true; | |
if(cur * 2 == y) | |
return curt + 1; | |
q.push(make_pair(cur * 2 ,curt + 1)); | |
} | |
if(cur * 3 <= y && !vis[cur * 3]){ | |
vis[cur * 3] = true; | |
if(cur * 3 == y) | |
return curt + 1; | |
q.push(make_pair(cur * 3 ,curt + 1)); | |
} | |
} | |
return -1; | |
} |
간단한 문제이다. 이것보다 어려운 문제를 풀어서 금방 생각이 났다. 하지만 한 테케가 틀렸는데 x 와 y가 같은 경우를 생각하지 못했다! 테케를 보자마자 생각이 났지만 테케를 보여주지 않았다면 보였을까..? 싶다
'코딩 > 프로그래머스' 카테고리의 다른 글
[프로그래머스] 택배 배달과 수거하기 (0) | 2023.03.16 |
---|---|
[프로그래머스] 시소 짝꿍 - C++ (0) | 2023.03.15 |
[프로그래머스] 인사고과 - C++ (0) | 2023.03.08 |
[프로그래머스] 연속 펄스 부분 수열의 합 - C++ (0) | 2023.03.06 |
[프로그래머스] 미로 탈출 - C++ (0) | 2023.03.06 |