[ SW ] 1808 지희의 고장난 계산기

문제

 

계산기에서 고장난 버튼과 사용가능한 버튼을 입력 받고

얻고자 하는 숫자를 사용가능한 버튼과 *와 = 버튼으로 만들수 있다면 최소 버튼 누른 횟수를 출력하고

얻고자 하는 숫자를 만들지 못한다면 -1을 출력하면 되는 문제이다.

 

 

 

문제 해결 방법

 

완전 탐색으로 문제 해결가능하다.

얻고자 하는 숫자를 n으로 부르겠습니다.

이 문제를 해결하기 위한 키포인트는 n에 약수들을 이용해서 문제를 해결하는 것입니다.

 

먼저 2가지 케이스로 나눌 수 있습니다.

1. 곱하기 연산을 사용 안하고 n을 구할 수 있는 경우

2. 곱하기 연산을 사용해서 n을 구할 수 있는 경우

 

곱하기 연산을 사용해서 n을 구할 때 bfs를 통해서 약수들 끼리 곱해서 얻으시면 됩니다.

예외 처리가 까다롭지만 예외 처리만 잘 해주시면 됩니다.

 

 

 

 

소스 코드

 

https://github.com/jokerKwu/BOJ_Algorithm/blob/master/SW%20expert%20Academy/Study_1808.cpp