사과 따기 게임 (21)

#2828: 사과 따기 게임(acmicpc.net)

아주 열심히 풀고 완벽한 알고리즘으로 풀었다… 라고 생각했다.

#include<bits/stdc++.h>
using namespace std;
int N, M, J, apple, ret;
int barket = 1;

int get(int now, int fall){
	int cnt = 0;
	if(fall >= now){ // 사과가 오른쪽에 떨어졌음 
		if(fall - now > M){ // 바구니에 담기 위해 이동(바깥에 떨어짐) 
			cnt = fall - M;
			barket = barket + fall - M;
		}
	}
	else{  // 사과가 왼쪽에 떨어졌음 if(fall < now)
		 cnt = now - fall;
		 barket = fall;
	}
	return cnt;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> M;
	cin >> J;
	for(int i = 0; i < J; i++){
		cin >> apple;
		
		ret += get(barket, apple);
	}
	cout << ret << "\n";
}

왜 틀렸어…? 한참을 보다가 물 한 잔을 마시자마자 바로 보았다. 사람이 마침내 그것이 수학 문제 또는 이와 유사한 문제라는 것을 깨닫게 되면 무엇이 잘못되었는지 말하기가 어려워 보입니다.

#include<bits/stdc++.h>
using namespace std;
int N, M, J, apple, ret;
int barket = 1;

int get(int now, int fall){
	int cnt = 0;
	if(fall >= now){ // 사과가 오른쪽에 떨어졌음 
		if(fall - now > M-1){ // 바구니에 담기 위해 이동(바깥에 떨어짐) 
			cnt = fall - now - M + 1;
			barket = barket + fall - now - M + 1;
		}
	}
	else{  // 사과가 왼쪽에 떨어졌음 if(fall < now)
		 cnt = now - fall;
		 barket = fall;
	}
	return cnt;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> M;
	cin >> J;
	for(int i = 0; i < J; i++){
		cin >> apple;
		
		ret += get(barket, apple);
	}
	cout << ret << "\n";
}

사과가 바구니 오른쪽으로 떨어지면 완전히 틀렸습니다. 우선 if 문의 조건부터 그림을 그리면서 문제를 생각했을 때 문제가 있었고 그에 따라 움직이는 부분을 생각해야 했습니다. now + M – 1 + ‘이동 거리’ = 떨어지므로 이동 거리 cnt를 재정렬하면

cnt = 가을 – 현재 – M + 1; 이에 따라 하단 바스켓(바스켓이 아닌 지금 바스켓이라고 부르는 이유는?)도 원래 바스켓+cnt라서 바꿔서 정답이 되었어요!

* 다른 분들의 풀이를 보면 사과가 바구니 양 끝 사이에 떨어지는지 아닌지의 값으로 풀이하는 풀이도 있습니다. 그것을 보면 이것이 내 솔루션보다 훨씬 덜 혼란스럽고 낫다고 생각합니다.