YEJIN LEE

“Keep turnin’ the pages”

2 minute read

그리디 알고리즘

문제

로니 콜먼 동영상을 보고 보디빌더가 되기로 결심한 향빈이는 PT 상담을 받으러 서강헬스클럽에 갔다. 향빈이가 서강헬스클럽을 선택한 이유는 PT를 받을 때 사용하는 운동기구를 회원이 선택할 수 있다는 점 때문이다. 하지만, 서강헬스클럽은 항상 사람이 많아서 PT를 한 번 받을 때 운동기구를 최대 두 개까지만 선택할 수 있다.

헬스장에 있는 $N$개의 운동기구를 한 번씩 사용해보고 싶은 향빈이는 PT를 받을 때마다 이전에 사용하지 않았던 운동기구를 선택하기로 계획을 세웠다. 그리고 비용을 절약하기 위해 PT를 받을 때 운동기구를 되도록이면 두 개를 사용하기로 했다. 예를 들어, 헬스장에 총 $10$개의 운동기구가 있을 경우 PT를 $5$번 받으면 모든 기구를 다 사용할 수 있다. $9$개의 운동기구가 있는 경우에도 PT를 $5$번 받지만, 마지막 PT를 받을 때는 운동기구를 하나만 사용한다.

하지만 향빈이는 운동기구를 선택하다가 큰 고민에 빠졌다. 왜냐하면 운동기구마다 근손실이 일어나는 정도가 다르기 때문이다. 어떤 운동기구는 자극이 잘 안 와서 근손실이 적게 일어나는데, 어떤 운동기구는 자극이 잘 와서 근손실이 많이 일어난다. 근손실이 죽음보다 무서운 향빈이는 PT를 한 번 받을 때의 근손실 정도가 $M$을 넘지 않도록 하고 싶다. 이때, $M$의 최솟값을 구해보자. 참고로, 운동기구를 두 개 사용해서 PT를 받을 때의 근손실 정도는 두 운동기구의 근손실 정도의 합이다.

입력

첫째 줄에 서강헬스클럽에 비치된 운동기구의 개수를 나타내는 정수 $N$이 주어진다.
($1 \leq N \leq 10\ 000$)

둘째 줄에는 각 운동기구의 근손실 정도를 나타내는 정수 $t_1, t_2, \cdots, t_N$가 주어진다.
($0 \leq t_i \leq 10^{18}$)

출력

$M$의 최솟값을 출력한다.

예제 입력 1 
5
1 2 3 4 5

예제 출력 1 
5

💻코드

/*
* [백준 16935] A -> B
* 정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.

* 2를 곱한다.
* 1을 수의 가장 오른쪽에 추가한다.

* A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

* [알고리즘]
* 그리디 알고리즘 : 현재 시점에서 best performance를 내기 위한 step을 선택하는 알고리즘으로, 각 단계에서 최선의 선택을 통해 전체적으로 best performance를 수행하는 것이 목적이다.
*
* B->A 방향으로 생각한다
	1. 짝수이면 2로 먼저 나눈다
	2. 홀수인 경우 1의자리가 1이면 1을 제거한다
	3. 그 외의 경우 -1을 리턴한다
	이 때, B가 1인 경우 무한루프에 빠지지않도록 한다
*/
#include<iostream>
#include<algorithm>	
#include<string>
#include<vector>	

using namespace std;

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

	int res = 0;

	while (B != A) {
		if (B % 2 == 0) {
			res++;
			B /= 2;
		}
		else if (B % 10 == 1 && B != 1) {
			res++;
			B /= 10;
		}
		else {
			cout << -1;
			return 0;
		}
	}
	cout << res + 1;
	return 0;
}

You may also enjoy