🔨 문제
https://www.acmicpc.net/problem/11034
<요약>
캥거루 세 마리가 수직선에 있고, 캥거루는 서로 다른 한 좌표 위에 있다.
한 번 움직일 때, 바깥쪽의 두 캥거루 중 한 마리가 다른 두 캥거루 사이의 정수 좌표로 점프할 때 캥거루가 최대 몇 번 움직일 수 있는지 출력하는 문제
🔨 해결방법
이 문제를 자세히 보면 '여러 개의 테스트 케이스', '각 테스트에 대해' 라는 표현으로 몇 번 입력 받을 것인지에 대해 정확히 알려주지 않는다.
이 때에는 EOF(End Of File, 사용자가 입력을 멈출 때까지 입력을 받음)를 사용한다. 난 몰라서 순진하게 정확히 예제를 기준으로 while문을 작성했고 3트로 맞았습니다를 봤다. ㅎㅎ
while(cin >> a >> b) {...}이런식으로 while문 안의 조건식에 입력을 받게 함으로써 입력 받을 때까지 출력하는식으로 조건식이 참이면 true, 거짓이면 false를 반환한다.
문제는 간단한데, 캥거루들이 서있는 좌표의 차이를 구하고 그 차이가 더 큰 쪽으로 캥거루를 이동시키는 것이다. (하지만 무조건 오름차순으로 주어지는 것이 아니기 때문에 sort필요)
다른 사람들 풀이를 보니 이 좌표의 차이를 구한 값의 최댓값-1을 바로 출력하던데 이건 생각 못했다! 어차피 캥거루가 한 번 뛰면 계속 같은 방향으로 이동하면서 차이가 1이 되더랑
ex. <1,5,9> => <5,6,9> => <6,7,9> => <7,8,9>
<1,5,9> => <1,4,5> => <1,3,4> => <1,2,3>
<3,5,9> => <5,6,9> => <6,7,9> => <7,8,9>
🔨 코드
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
cin.tie(NULL);
cout.tie(NULL);
ios::sync_with_stdio(false);
int num[4] = { 0 };
while (cin >> num[0] >> num[1] >> num[2]) {
sort(num, num + 3);
int dist1=0, dist2 = 0;
int cnt = 0;
while (1) {
dist1 = num[1] - num[0], dist2 = num[2] - num[1];
if (dist1 == 1 && dist2 == 1) break;
if (dist1 >= dist2) {
num[2] = num[1];
num[1] = num[1] - 1;
cnt++;
}
else {
num[0] = num[1];
num[1] = num[1] + 1;
cnt++;
}
}
cout << cnt<< '\n';
}
return 0;
}EOF
https://st-lab.tistory.com/257
그리디 알고리즘
https://namu.wiki/w/%EA%B7%B8%EB%A6%AC%EB%94%94%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
그리디 알고리즘은 말 그대로 욕심쟁이 알고리즘이다. 매 선택에서 가장 최적인 답을 선택하는 방식으로 진행하며 최종적인 해답에 도달
매 선택은 그 순간에 대해서는 최적이지만, 최종적으로 최적이라는 보장은 없다.
