[C++] 프로그래머스 Lv.2 숫자 변환하기

문제 링크

• https://school.programmers.co.kr/learn/courses/30/lessons/154538

풀이 방법

• dist 배열을 조건의 최대 크기로 설정
• dist의 모든 원소를 -1로 초기화
• dist가 -1 이고 범위를 넘어가지 않는다면 현재 값에 +1을 하여 저장
• 큐가 빌 때까지 돌고 끝나면 dist[y]를 리턴

실패 풀이

• DFS로 풀이를 제출하니 50점으로 시간초과가 나왔다.

코드

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int dist[1000001];
int solution(int x, int y, int n) {
	queue<int> q;
	fill(dist, dist + 1000001, -1);
	dist[x] = 0;
	q.push(x);

	while (!q.empty())
	{
		auto cur = q.front();
		q.pop();
		for (auto next : { cur + n,cur * 2,cur * 3 })
		{
			if (next < 0 || next>y) continue;
			if (dist[next] != -1) continue;
			dist[next] = dist[cur] + 1;
			q.push(next);
		}
	}
	return dist[y];
}

기억하기

for (auto next : { cur + n,cur * 2,cur * 3 })