[백준 알고리즘] 17174번 : 전체 계산 횟수

문제

호근이는 한국에서 미국으로 유학을 하러 갔다. 그는 생활비로 쓰기 위해 가지고 온 원화를 전부 달러로 바꾸기 위해 환전소를 찾아갔다. 그런데 환전소에 1달러짜리 지폐를 제외하고는 다른 지폐가 없어서 전부 1달러 지폐로 바꾸어 숙소로 가져왔다. 환전한 금액을 알고 있지만 불안한 마음에 숙소에서 다시 한 번 얼마인지 세어 보려고 한다.

호근이는 우선 1달러 지폐를 한 장씩 세면서 M개의 지폐를 한 묶음으로 만든다. 그 다음에는 새로 만들어진 묶음을 하나씩 세면서 M개의 묶음을 다시 하나로 묶는다. 더 이상 묶음이 만들어지지 않을 때까지 이 과정을 반복한다. 이때 호근이가 묶음을 포함해 지폐를 센 전체 횟수를 구하여라.

예를 들어 N이 13이고 M이 10일 때, 13달러를 세기 위해서는 1달러씩 총 13번을 세고, 지폐 10장을 한 묶음으로 만들고, 한 개의 묶음을 다시 한 번 세어 총 14번을 세야 한다.

입력

첫 번째 줄에 환전한 금액 N과 묶음의 크기 M이 주어진다. (2 ≤ N ≤ 100,000, 2 ≤ M ≤ N)

출력

전체 센 횟수를 출력한다.

예제 입력 1

13 10

예제 출력 1

14

예제 입력 2

100 8

예제 출력 2

113

출처

University > 충남대학교 > 제3회 생각하는 프로그래밍 대회 B번

 

내가 작성한 코드 (C++ 성공)

#include <iostream>

using namespace std;

int main(){
	int n,m;
	cin >> n >> m;
	
	int cnt = n;
	
	while(n >= m) {
		n = n/m;
		cnt += n;
	}
	
	cout << cnt;
	
	return 0;
}

 

정리

생각보다 간단한 문제였지만 문제를 잘못 이해하는 바람에 몇번 틀리고나서 맞출 수 있었다.

내가 틀렸던 이유를 예를 들어 설명해보자면

100개를 8개의 묶음으로 묶어서 센다고 하면
일단 100개를 먼저 세기 때문에 100번을 센다.
그리고 100개를 8개로 묶는다. 그럼 8개씩 12 묶음이 나오기 때문에 12번을 또 센다.
그리고 12개의 묶음을 다시 8개로 묶는다. 그럼 8개씩 1묶음이 나오기 때문에 1번을 또 센다.
그래서 정답은 113번이 되는 것이다.

내가 틀렸던 부분은 위에서 밑줄 친 부분이다.
나는 한번만 묶어서 세어주는 줄 알고 묶음을 다시 묶어주는 것을 생각하지 않았다.
문제에 과정을 반복하라는 말이 나와있음에도 불구하고 정확히 제대로 이해하지 않고 풀었다.
다음에는 문제를 정확히 이해하고 풀어야겠다.