[level 2] 숫자 변환하기 - 154538

문제 링크

성능 요약

메모리: 4.2 MB, 시간: 0.09 ms

구분

코딩테스트 연습 > 연습문제

채점결과

정확성: 100.0
합계: 100.0 / 100.0

제출 일자

2024년 04월 11일 17:04:50

문제 설명

자연수 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

입출력 예

x	y	n	result
10	40	5	2
10	40	30	1
2	5	4	-1

입출력 예 설명

입출력 예 #1
x에 2를 2번 곱하면 40이 되고 이때가 최소 횟수입니다.

입출력 예 #2
x에 n인 30을 1번 더하면 40이 되고 이때가 최소 횟수입니다.

입출력 예 #3
x를 y로 변환할 수 없기 때문에 -1을 return합니다.

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges

풀이

소요시간 40분

처음에 dfs사용해서 풀었지만, 시간초과로 인하여 실패했다. 원인을 찾아보니 dfs를 사용하면 전체를 다 돌기 때문에 시간이 오래 걸린다. 그래서 bfs 방법으로 풀었다.
최단경로는 bfs방식으로 먼저 풀어봐야겠다는 생각이 들었다.

나의 틀린 풀이

  
#include <string>
#include <vector>
#include <iostream>
#include <limits.h>
using namespace std;

// dp를 사용해서 회수를 저장하자
int ans = INT_MAX;
void dfs(int x,int y,int n,int cnt)
{
    
    if(x==y){
        if(ans>cnt) ans = cnt;
    }
    else if(x>y) {}
    else
    {   
        cnt++;
        dfs(x*3,y,n,cnt);

        dfs(x*2,y,n,cnt);

        dfs(x+n,y,n,cnt);
    }   
}

int solution(int x, int y, int n) {
    int answer = 0;
    dfs(x,y,n,0);

    return ans!=INT_MAX ? ans : -1;
}

나의 정답 풀이

  
#include <queue>
#include <vector>
#include <iostream>
#include <limits.h>

using namespace std;

int solution(int x, int y, int n) {
    if(x==y) return 0;
    int answer = 0;
    vector<bool> visited(y + 1, false); // 방문 여부를 저장하는 배열
    queue<pair<int, int>> q; // BFS를 위한 큐
    q.push({x, 0}); // 시작 위치와 이동 횟수(0)를 큐에 추가
    visited[x] = true; // 시작 위치 방문 처리
    
    while(!q.empty())
    {
        int location = q.front().first;
        int cnt = q.front().second;
        q.pop();
        
        if (curPos == y) { // 목표 위치에 도달한 경우
        answer = curCnt; // 현재 이동 횟수가 최소값이므로 정답에 저장하고 종료
        break;
        }
        
        // 값을 넣어준다. 아니면 continue
        
        // 다음 이동 가능한 위치를 탐색하고 큐에 추가
        if (curPos * 3 <= y && !visited[curPos * 3]) {
            q.push({curPos * 3, curCnt + 1});
            visited[curPos * 3] = true;
        }
        if (curPos * 2 <= y && !visited[curPos * 2]) {
            q.push({curPos * 2, curCnt + 1});
            visited[curPos * 2] = true;
        }
        if (curPos + n <= y && !visited[curPos + n]) {
            q.push({curPos + n, curCnt + 1});
            visited[curPos + n] = true;
        }
    }
    
    
}

programmers 2단계 숫자변환하기