[백준/C++] 16953 A → B

2023. 11. 8. 08:11· Algorithm
목차
  1. 내 코드
  2. 다른 풀이
728x90
유형 난이도 완료일 링크 특이사항
백트래킹 실버2 23.04.04 https://www.acmicpc.net/problem/16953  

 

 

내 코드

#include <iostream>

using namespace std;

int a, b;
int MIN = 1000000000;

void DFS(long long int n, int depth)
{
	if(n == b && depth<MIN)
	{
		MIN = depth;
		return;
	}
	
	if(n > b)
		return;
	
	DFS(n*2, depth+1);
	DFS(n*10+1, depth+1);
}

int main(void)
{
	cin >> a>> b;
	
	DFS(a,1);
	
	if(MIN == 1000000000)
		MIN = -1;
	cout<< MIN;
}

a에 *2를 하거나 *10+1을 반복하여 b가 되는 최소의 경우를 찾는 문제. 선택지가 두 개 이므로 경우의 수를 나열해보면 트리 구조로 표현할 수 있다. 트리를 순회하는 DFS나 BFS로 모든 가능한 경우를 따져보고 최소 경우를 출력한다.

다른 풀이

#include <stdio.h>
#include <queue>
using namespace std;

int main(){
	int A,B;
	int ans = -1;
	queue<pair > q;
	
	scanf("%d %d",&A,&B);
	
	q.push(make_pair(A,1));
	
	while(!q.empty()){
		long long int k = q.front().first;
		int n = q.front().second;
		q.pop();
		
		if(k==B){
			ans = n;
			break;
		}
		
		if(k*2<=B)
			q.push(make_pair(k*2,n+1));
		if(k*10+1<=B)
			q.push(make_pair(k*10+1,n+1));
	}
	
	printf("%d",ans);
	
	return 0;
}
//https://rujang.tistory.com/entry/%EB%B0%B1%EC%A4%80-16953%EB%B2%88-A-%E2%86%92-B-CC

큐를 이용한 풀이다. 연산하는 값을 담는 int와 연산 횟수를 담는 int 두 가지를 가지는 pair를 큐에 담는다. 큐에 들어온 특정 값에 대해 B를 초과하지 않는다면 두 가지 연산을 모두 진행하여 큐에 담고 큐가 빌 때까지 반복문이 실행되기 때문에 결국 모든 경우를 다룰 수 있다. 그리고 연산 횟수가 적은 경우부터 순서대로 계산되기 때문에 정답을 찾는 순간 출력하면 그것이 최소 경우가 된다.

큐를 이용해서 모든 경우를 탐색하는 방법에 대해 생각해보지 못했다. 큐도 적극 활용해야겠다.

728x90

'Algorithm' 카테고리의 다른 글

[백준/C++] 1629 곱셈  (0) 2023.11.08
[백준/C++] 11660 구간 합 구하기 5  (0) 2023.11.08
[백준/C++] 11725 트리의 부모 찾기  (0) 2023.10.25
[백준/C++] N과 M(12)  (0) 2023.10.25
[백준/C++] 15663 N과 M(9) (S2)  (0) 2023.10.25
  1. 내 코드
  2. 다른 풀이
'Algorithm' 카테고리의 다른 글
  • [백준/C++] 1629 곱셈
  • [백준/C++] 11660 구간 합 구하기 5
  • [백준/C++] 11725 트리의 부모 찾기
  • [백준/C++] N과 M(12)
Yannoo
Yannoo
개발 관련 정보 보관
250x250
Yannoo
YannooLog
Yannoo
전체
오늘
어제
  • 분류 전체보기 (60)
    • Unity (6)
    • Algorithm (52)
    • Flutter (0)
    • Firebase (0)
    • Unreal (2)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 문자열
  • DFS
  • 그래프
  • 알고리즘
  • 백트래킹
  • 그리디
  • 시간복잡도
  • 냅색
  • 백준
  • 배열
  • DP
  • c++
  • BFS
  • 정수론
  • 이진탐색
  • 트리

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.1
Yannoo
[백준/C++] 16953 A → B
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.