1463번: 1로 만들기
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
www.acmicpc.net
과거에 올린 BOJ 1697 숨바꼭질 과 동일한 문제이다.
다만 차이가 있다면 숨바꼭질은 +1, -1, *2 연산을 허용했다면 이번 문제는 -1, /2, /3 연산을 허용한다는 것만 다르다.
그래서 이번에는 숨바꼭질 문제와 반대로 목적지 ( = 1)에서 시작하여 역연산 (*2, *3, +1)을 하여 답을 찾아보기로 한다.
규칙은 아래와 같다.
- (규칙 A) 현재 도달 가능한 숫자를 큐에 저장한다.
- (규칙 B) 저장된 숫자를 하나씩 꺼내어 *2 / *3 / +1 연산을 해준다.
- (규칙 C) 규칙 B에 의해 연산된 결과에 해당하는 숫자가 기존에 탐색되지 않았다면, 해당 숫자에 현재 횟수 +1의 값을 준다.
- (규칙 D) 목표에 도착할 때까지 A~C의 규칙을 반복한다.
code
GitHub - YoungWoo93/algorithmOnlineJudge: 알고리즘 온라인 저지
알고리즘 온라인 저지. Contribute to YoungWoo93/algorithmOnlineJudge development by creating an account on GitHub.
github.com
'알고리즘 온라인 저지 > BOJ' 카테고리의 다른 글
| BOJ 2042번 구간 합 구하기 (0) | 2022.02.07 |
|---|---|
| BOJ 16964 DFS 스페셜 저지 (0) | 2022.02.03 |
| BOJ 1339 단어 수학 (0) | 2022.01.30 |
| BOJ 2178 미로 탐색 (0) | 2022.01.28 |
| BOJ 1238 파티 (0) | 2022.01.28 |
