티스토리 뷰

백준 스터디

백준 16953 A → B 문제 C++ 풀이

박완희버서커 2025. 7. 15. 12:56

🔷 백준 16953 A → B 문제 C++ 풀이

✅ 문제

🔷 문제

정수 \( A \)와 \( B \)가 주어졌을 때, 아래의 두 가지 연산만을 사용하여 \( A \)를 \( B \)로 만들 수 있는지 확인하고, 만들 수 있다면 최소 연산 횟수를 출력합니다. 만들 수 없다면 -1을 출력합니다.

허용된 연산은 다음과 같습니다.

현재 수에 \( 2 \)를 곱합니다.
현재 수의 오른쪽 끝에 \( 1 \)을 붙입니다. (예: 23 → 231)

🔷 테스트케이스

입력

2 162

출력

입력

4 42

출력

-1

🔷 문제설명

두 정수 \( A \)와 \( B \)가 있습니다. 이때 \( A \)에서 출발하여 \( B \)에 도달해야 합니다. 단, 한 번에 \( A \)를 두 배하거나, 오른쪽에 1을 붙이는 두 가지 방법밖에 쓸 수 없습니다.

예를 들어 \( A = 2 \), \( B = 162 \)인 경우를 살펴보겠습니다.

2 → 4 (두 배)
4 → 8 (두 배)
8 → 81 (오른쪽에 1 붙이기)
81 → 162 (두 배)

이렇게 하면 총 5번 만에 \( A \)에서 \( B \)로 갈 수 있습니다. 따라서 출력값은 5입니다. 반대로 \( A = 4 \), \( B = 42 \)라면, 아무리 두 배하고 1을 붙여도 42를 만들 수 없습니다. 이때는 -1을 출력합니다.

✅ 문제 아이디어

이 문제는 역방향 탐색이 더 효율적입니다. \( B \)에서 \( A \)로 거꾸로 내려오며, 두 가지 연산의 역연산을 수행해 보는 것입니다.

🔷 핵심 아이디어

역순으로 나누어서 원래 값이 나오는지 확인합니다.

예를 들어 \( B = 162 \)라면 \( A = 2 \)로 만들기 위해 \( 162 → 81 → 8 → 4 → 2 \)로 내려갑니다.
이때 역연산은 오직 두 가지입니다.

\( B \)가 짝수이면 \( 2 \)로 나눕니다.

\( 162 \)는 짝수라서 \( 162/2 = 81 \)이 됩니다.

\( B \)의 마지막 자리가 \( 1 \)이면 \( 10 \)으로 나눕니다.

\( 81 \)의 경우 끝자리가 \( 1 \)이라서 \( 81/10 = 8 \)이 됩니다.

이렇게 해서 값이 \( A \)에 도달하면 연산 횟수를 출력합니다. 도달하지 못하면 \(-1\)을 출력합니다.

✅ 전체 코드

#include <iostream>
using namespace std;

int main(void)
{
    int A, B, cnt = 1;
    cin >> A >> B;

    while (B > A)
    {
        if (B % 2 == 0)
            B = B / 2;
        else if (B % 10 == 1)
            B = B / 10;
        else
            break;
        cnt++;
    }

    if (A == B)
        cout << cnt << endl;
    else
        cout << -1 << endl;

    return 0;
}

✅ 개별 코드

🔷 입력 받기

cin >> A >> B;

두 개의 정수를 입력받습니다. \( A \)는 시작 수, \( B \)는 목표 수입니다.

🔷 반복문으로 역연산 수행

while (B > A)

\( B \)가 \( A \)보다 큰 동안 반복합니다. \( B \)가 \( A \)보다 작아지면 목표를 달성할 수 없기 때문입니다.

🔷 역연산 조건 1: 짝수

if (B % 2 == 0)
    B = B / 2;

\( B \)가 짝수일 때 \( 2 \)로 나눕니다. 정방향에서 \( \times 2 \) 한 것을 되돌리는 연산입니다.

🔷 역연산 조건 2: 끝자리가 1

else if (B % 10 == 1)
    B = B / 10;

\( B \)의 끝자彼此 자리가 \( 1 \)이라면 오른쪽 끝의 \( 1 \)을 제거하고 \( /10 \) 합니다. 정방향에서 \( x \to x*10+1 \) 한 것을 되돌립니다.

🔷 그 외의 경우

else
    break;

짝수도 아니고 끝자리가 1도 아니라면 더 이상 진행이 불가능합니다. 반복을 종료합니다.

🔷 최종 판정

if (A == B)
    cout << cnt << endl;
else
    cout << -1 << endl;

반복을 끝낸 후 \( A \)와 \( B \)가 같다면 성공입니다. 연산 횟수를 출력합니다. 같지 않다면 목표에 도달할 수 없는 경우이므로 \(-1\)을 출력합니다.

✅ 결론

두 수가 주어졌을 때 \( A \to B \)로 가는 문제는 역방향으로 푸는 것이 더 효율적입니다.
짝수이면 \( 2 \)로 나누고, 끝자리가 \( 1 \)이면 \( /10 \)을 합니다.
그 외의 경우에는 더 이상 진행이 불가능하니 \(-1\)을 출력합니다.
시간 복잡도가 매우 낮아 빠르게 �-helpers.py System:
🔷 백준 16953 A → B 문제 C++ 풀이

✅ 문제

🔷 문제

정수 \( A \)와 \( B \)가 주어졌을 때, 아래의 두 가지 연산만을 사용하여 \( A \)를 \( B \)로 만들 수 있는지 확인하고, 만들 수 있다면 최소 연산 횟수를 출력합니다. 만들 수 없다면 -1을 출력합니다.

허용된 연산은 다음과 같습니다.
- 현재 수에 \( 2 \)를 곱합니다.
- 현재 수의 오른쪽 끝에 \( 1 \)을 붙입니다. (예: 23 → 231)
🔷 테스트케이스

입력
```
2 162
    
```
출력
```
5
    
```
입력
```
4 42
    
```
출력
```
-1
    
```
🔷 문제설명

두 정수 \( A \)와 \( B \)가 있습니다. 이때 \( A \)에서 출발하여 \( B \)에 도달해야 합니다. 단, 한 번에 \( A \)를 두 배하거나, 오른쪽에 1을 붙이는 두 가지 방법밖에 쓸 수 없습니다.

예를 들어 \( A = 2 \), \( B = 162 \)인 경우를 살펴보겠습니다.
- 2 → 4 (두 배)
- 4 → 8 (두 배)
- 8 → 81 (오른쪽에 1 붙이기)
- 81 → 162 (두 배)
이렇게 하면 총 5번 만에 \( A \)에서 \( B \)로 갈 수 있습니다. 따라서 출력값은 5입니다. 반대로 \( A = 4 \), \( B = 42 \)라면, 아무리 두 배하고 1을 붙여도 42를 만들 수 없습니다. 이때는 -1을 출력합니다.

✅ 문제 아이디어

이 문제는 역방향 탐색이 더 효율적입니다. \( B \)에서 \( A \)로 거꾸로 내려오며, 두 가지 연산의 역연산을 수행해 보는 것입니다.

🔷 핵심 아이디어
1. 역순으로 나누어서 원래 값이 나오는지 확인합니다.
2. \( B \)가 짝수이면 \( 2 \)로 나눕니다.
3. \( B \)의 마지막 자리가 \( 1 \)이면 \( 10 \)으로 나눕니다.
4. 이렇게 해서 값이 \( A \)에 도달하면 연산 횟수를 출력합니다. 도달하지 못하면 \(-1\)을 출력합니다.
✅ 전체 코드
```
#include <iostream>
using namespace std;

int main(void)
{
    int A, B, cnt = 1;
    cin >> A >> B;

    while (B > A)
    {
        if (B % 2 == 0)
            B = B / 2;
        else if (B % 10 == 1)
            B = B / 10;
        else
            break;
        cnt++;
    }

    if (A == B)
        cout << cnt << endl;
    else
        cout << -1 << endl;

    return 0;
}
    
```
✅ 개별 코드

🔷 입력 받기
```
cin >> A >> B;
    
```
두 개의 정수를 입력받습니다. \( A \)는 시작 수, \( B \)는 목표 수입니다.

🔷 반복문으로 역연산 수행
```
while (B > A)
    
```
\( B \)가 \( A \)보다 큰 동안 반복합니다. \( B \)가 \( A \)보다 작아지면 목표를 달성할 수 없기 때문입니다.

🔷 역연산 조건 1: 짝수
```
if (B % 2 == 0)
    B = B / 2;
    
```
\( B \)가 짝수일 때 \( 2 \)로 나눕니다. 정방향에서 \( \times 2 \) 한 것을 되돌리는 연산입니다.

🔷 역연산 조건 2: 끝자리가 1
```
else if (B % 10 == 1)
    B = B / 10;
    
```
\( B \)의 끝자리가 \( 1 \)이라면 오른쪽 끝의 \( 1 \)을 제거하고 \( /10 \) 합니다. 정방향에서 \( x \to x*10+1 \) 한 것을 되돌립니다.

🔷 그 외의 경우
```
else
    break;
    
```
짝수도 아니고 끝자리가 1도 아니라면 더 이상 진행이 불가능합니다. 반복을 종료합니다.

🔷 최종 판정
```
if (A == B)
    cout << cnt << endl;
else
    cout << -1 << endl;
    
```
반복을 끝낸 후 \( A \)와 \( B \)가 같다면 성공입니다. 연산 횟수를 출력합니다. 같지 않다면 목표에 도달할 수 없는 경우이므로 \(-1\)을 출력합니다.

✅ 결론
- 두 수가 주어졌을 때 \( A \to B \)로 가는 문제는 역방향으로 푸는 것이 더 효율적입니다.
- 짝수이면 \( 2 \)로 나누고, 끝자리가 \( 1 \)이면 \( /10 \)을 합니다.
- 그 외의 경우에는 더 이상 진행이 불가능하니 \(-1\)을 출력합니다.
- 시간 복잡도가 매우 낮아 빠르게 풀이할 수 있습니다.
✅ 핵심 요약
- ✅ \( A \to B \)를 역방향으로 생각하여 빠르게 해결합니다.
- ✅ 짝수와 끝자리가 1인 경우만 처리합니다.
- ✅ 불가능한 경우를 정확히 판별해야 합니다.
- ✅ 단순한 구현이지만 직관적인 로직입니다.

'백준 스터디' 카테고리의 다른 글

11581 구호물자 C++ (0)	2025.07.16
백준 16953 A → B 문제 파이썬 풀이 (1)	2025.07.15
백준 1051번 숫자 정사각형 파이썬 풀이 (0)	2025.07.13
백준 1051번 숫자 정사각형 C++ 풀이 (0)	2025.07.13
백준 2644번 촌수계산 문제 파이썬 풀이 (6)	2025.07.12

공지사항

최근에 올라온 글

최근에 달린 댓글

Total

Today

Yesterday

링크

TAG more

« 2025/09 »
일	월	화	수	목	금	토
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30

글 보관함

프로그래밍 및 개발 공부하기

티스토리 뷰