문제 설명
자연수 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
입출력 예 설명
입출력 예 #1x에 2를 2번 곱하면 40이 되고 이때가 최소 횟수입니다.
입출력 예 #2x에 n인 30을 1번 더하면 40이 되고 이때가 최소 횟수입니다.
입출력 예 #3x를 y로 변환할 수 없기 때문에 -1을 return합니다.
해설
나도 못풀어서 다른 사람 풀이를 봤다.
우선, 테스트 6번 케이스는 x와 y가 같다. 그래서 x == y일 때를 0으로 리턴해주는 전처리가 필요하다.
우선 deque를 써써 큐 + 스택 구조를 만든다.
while문을 돌려서 y와 first, second, third 중 하나가 같을 때까지 돌리게 한다.
for문을 안에 돌려서 arr개수 만큼 돌리는데,
arr에서 왼쪽 값을 빼서 num이라는 변수에 담고
이를 각각 first, second, third라는 식으로 계산한다.
y와 같지 않다면
first 값은 y보다 작을것이고, 만든 check 리스트에 1을 담는다.
그리고 arr에 first든 second, third 든 담아서 다시 for문을 돌린다.
lv2부터는 stack, 동적프로그래밍, bfs,dfs 가 주로 나오니 레벨 2만 풀수 있으면 대기업 외에는 합격권일 것 같다.
스타트업에서 엄청 어려운 문제가 나오는건 못봤던것 같아서...?
근데 확실히 lv2부터 어렵긴 한것 같다. 천천히 하다보면 되겠지
