[백준/c++] 17296 - But can you do it in 0.5x A presses?

https://www.acmicpc.net/problem/17296

17296번: But can you do it in 0.5x A presses?

---

요새 블로그 글을 통 안 적어서, 한꺼번에 모아서 적을려다가

내가 문제 이해하는 데에만 너무 많은 시간을 쏟아부은 문제가 있어 이렇게 적는다😥

나도 이해가 되게 적을 수 있을지는 모르겠지만, 나 같은 사람이 좀 적어졌으면 하는 마음으로 써보겠다!

1) 풀이

" 음이 아닌 정수 x에 대해 x+0.5라는 것은 정말로 A버튼을 x+0.5번 누르라는 뜻이 아니라, A버튼을 누른 채로 스테이지를 시작한 뒤 A버튼을 x번 더 누르라는 뜻이다. 그 스테이지만 골라서 깨려고 한다면 A버튼을 총 x+1번 눌러야 하지만, A버튼을 누른 채로 이전 스테이지를 깨고 그 상태로 다음 스테이지를 시작한 경우라면 x번만 눌러도 되는 것이다.

내가 이문제에서 이해 못했던 대목부터 짚고 넘어가보도록 하겠다.

사실 지금에서야 저 대목을 읽어보면, 진짜 말 그대로인데 조금 어렵게 설명이 되어있는 것 같다.

 

예시를 들어 설명해보도록 하겠다.

가령, 특정 스테이지에서 A버튼을 누르는 최소횟수가 1.5번이라고 하자.

문제에서도 적혀있듯, 실제로 버튼을 0.5번 누르는 것은 불가능하다.

결론적으로 말하면 0.5는 진짜로 버튼을 누르는 횟수가 아니라

'너 이 스테이지를 시작할때 버튼 누르고 있어야 한다.'라는 뜻이다.

그러니까 1.5=1+0.5, 이 스테이지 시작할때 버튼을 누르고 있고 진행하면서 1번 더 누르라는 의미이다.

계속해서 예시로 설명을 이어보자면, 이 예시에서는 1.5 즉  시작할 때 버튼을 누르고 있어야 하므로, 이 특정 스테이지 하나만 깬다면 이전에 버튼을 누른 적이 없기 때문에 시작할때 1번+그리고 진행하면서 1번 총 두번 누르는 게 맞지만, 이전 스테이지에서부터 계속 누르고 있었다면 버튼을 시작할 때 누를 필요없기 때문에 1번만 누르면 된다.

 

이와 같은 경우를 코드를 짜기 위해 좀 더 깔끔하게 바꿔보면 다음과 같다.

 

1. 이전 스테이지에서 버튼을 누른 적이 없는 경우

1-1. 주어진 횟수가 정수번인 경우 (x번인 경우)

1-2. 주어진 횟수가 정수번이 아닌 경우(x+0.5번인 경우)

2. 이전 스테이지에서 버튼을 이미 누른 경우

 

문제에서, 버튼을 계속 누르고 있어도 아무 문제 없다고 해주었고 우리는 최소로 횟수를 구해야 하기 때문에

버튼이 한 번이라도 눌렸다면 계속 누르고 있다고 가정하면 된다.

즉, 이전에 버튼이 한 번이라도 눌린 적 있다면 모두 2의 경우로 처리해주면 된다.

 

말이 나온 김에 2의 경우부터 먼저 설명해보자면,

최소횟수가 0인 스테이지를 제외하고는 floor 함수를 이용해 소수점 자리를 버린 횟수를 총합 변수에 더하면 된다.

floor함수는 어떤 수의 소수점 자리를 버리는 버림함수인데, 좀 더 자세한 내용은 3) 참고자료를 참고하길 바란다.

 

그리고 1의 경우에 다시 주어진 횟수가 1) x번인 경우와 2) x+0.5번인 경우로 나눌 수 있는데

x번인 경우는 시작할 때 버튼을 따로 눌러줄 필요 없다는 의미이므로 그냥 x번을 총합 변수에 더해주면 되고

x+0.5의 경우에는 시작할 때 버튼을 눌러주라는 의미인데, 이전에 버튼이 눌린 경우가 없으므로 x+1을 총합 변수에 더해준다.

1의 경우가 끝나면, 버튼이 한 번이라도 눌렸으므로 bool 변수를 통해 버튼이 눌린 것을 처리해주면 된다.

 

장황하게 설명을 해놓으니, 내가 설명한 것도 다소 어려워보이긴 한다,,

그래두 최대한 풀어서 설명을 해봤으니 아래 코드와 함께 놓고 보면 이해가 더 잘 갈 것 같다.

혹시 질문이 있거나 틀린 부분이 있다면 댓글에 적어주시길!

 

2) 최종 소스코드

#include <bits/stdc++.h>
using namespace std;
int n;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	int sum = 0; //최소횟수 총합
	bool press = false; //버튼을 눌렀는지에 대한 여부. true 면 누른것.
	for (int i = 0; i < n; i++) {
		double x;
		cin >> x; //스테이지를 깨는 데에 필요한 최소횟수
		if (x == 0) continue; //눌ㄹ
		double tmp = floor(x); //0.5를 버림한다
		if (press == false) { //아직 버튼이 한 번도 눌리지 않은 상태
				if (tmp == x) { //최소횟수가 x인 경우
					sum += tmp;
				}
				else { //최소횟수가 x+0.5 인 경우 
					sum += tmp + 1;
				}
				press = true;
		}
		else { //이전 스테이지에서 버튼이 눌린 상태
			if (tmp == 0) continue; 
			else {
				sum += tmp;
			}
		}
	}
	cout << sum << '\n';
}

3) 참고자료

http://soen.kr/lecture/ccpp/cpp1/8-1-4.htm