https://9oormthonchallenge.oopy.io/
문제
접근
- 주어진 수열이 가장 값이 높은 값을 기준으로 양 끝으로 갈수록 감소하거나 같아야 한다.
- 다르게 생각하면 주어진 수열이 단조 증가 상태에서 단조 감소 상태로 1번만 바뀌어야 한다.
구현
#include <stdio.h>
int main() {
int n;
scanf("%d", &n);
int i = 0;
int ret = 0, prev = 0, now;
// 단조 증가 while loop
while (i++ < n) {
scanf("%d", &now);
ret += now;
if (now < prev) break;
prev = now;
}
// 단조 감소 while loop
prev = now;
while (i++ < n) {
scanf("%d", &now);
ret += now;
// 단조 감소 while loop에서 증가하면
// 완벽한 햄버거가 아니라 0을 출력하고 끝냄
if (now > prev) {
printf("0\n");
return 0;
}
prev = now;
}
printf("%d\n", ret);
return 0;
}
- 하나씩 입력받으며 단조 증가하는 동안 값을 ret에 더해준다.
- 지금 입력받은 값이 전에 입력받은 값보다 작으면 while loop에서 빠져나온다.
- 다시 하나씩 입력받으며 단조 감소하는 동안 값을 ret에 더해준다.
- 지금 입력받은 값이 전에 입력받은 값보다 크면 수열이 단조 증가에서 단조 감소로 1번만 바뀌어야 한다는 조건에 맞지 않으므로(=완벽한 햄버거가 아니므로) 0을 출력하고 프로그램 종료한다.
- 종료되지 않고 while loop를 빠져나왔다는 것은, 주어진 조건에 맞으므로(=완벽한 햄버거) 모든 수열의 합(햄버거의 맛)을 출력하고 종료한다.
먼저 값을 다 입력받으며 최댓값의 위치를 저장하고, 다시 양 끝으로 가며 단조 감소하는지 확인해도 되지만, 완벽한 햄버거가 아닌 경우에 바로 종료하는 이 구현보다 느릴 수 있다.
처음에 2개의 while loop 사이의 prev = now;를 빼먹어서 틀렸다.
1 5 9 6 7 2 입력이 이렇게 들어올 때, 6을 입력받고 첫 번째 while loop를 탈출하면서 prev에 6이 저장되지 않고 그대로 9인 상태에서 두 번째 while loop에서 7을 입력받고 감소했다고 판단하고 종료되지 않고 그대로 진행되는 게 원인이었다.
조심하자!!
Jeongble