Notice
Recent Posts
Recent Comments
Link
궤도
[EPPER] 13회 7번 본문
문제
풀이
너무 어렵게 생각해서 시간이 좀 걸렸다. 단순하게 생각하면 된다. 양끝을 서로 비교한다. 그럼 이 셋 중 하나일 것이다.
1. 양끝 숫자가 같다.
2. 왼쪽 숫자 < 오른쪽 숫자
3. 왼쪽 숫자 > 오른쪽 숫자
1번의 경우라면 회문 조건을 충족하니 한칸씩 안으로 들어가면 된다. 2번의 경우라면 왼쪽 숫자가 커지도록 인접한 숫자와 더해주고, 3번의 경우라면 오른쪽 숫자가 커지도록 인접한 숫자와 더해준다. 재귀함수로 구현했는데, 반복문으로 구현해도 어려움은 없을 것 같다.
소스코드
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int cnt = 0;
int arr[10];
void pal(int start, int end) {
if (start == end || start > end)
return;
else if (arr[start] == arr[end])
pal(start + 1, end - 1);
else if (arr[start] < arr[end]) {
arr[start + 1] += arr[start];
pal(start + 1, end);
cnt++;
}
else {
arr[end - 1] += arr[end];
pal(start, end - 1);
cnt++;
}
}
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d", &arr[i]);
pal(0, n - 1);
printf("%d", cnt);
}
Comments