문제
각 팬케이크의 지름들이 주어졌을 때, 한 지점에서 뒤집는(Filp) 방식을 통해 지름이 큰 것은 아래로, 위로 올라갈수록 지름이 작은 팬케이크가 놓이게 쌓는 문제이다. EOF가 주어질 때까지 공백으로 구분되는 지름의 입력을 받고, 개수는 1-30 사이이다. 지름은 1-10 사이로 주어진다. 팬케이크의 위치는 맨 아래서부터 1, 맨 위가 n이다. 예를 들어, 전체를 뒤집는다 하면 filp(1)이 된다. 출력값은 첫번째 줄에 원래의 팬케이크 모양을 출력한 뒤, ()안에 정렬된 상태를 출력한다. 단, 이미 정렬된 상태는 그냥 팬케이크의 모양과 아래줄에 0을 출력하고 종료한다. 두번째 줄에는 어디에서 뒤집었는지 위치를 차례대로 출력한다. 아래 테스트 케이스를 확인하면 이해가 쉬울 듯 하다.
테스트케이스
input 1)
1 2 3 4 5
output 1)
1 2 3 4 5
0
input 2)
5 4 3 2 1
output 2)
5 4 3 2 1 (1 2 3 4 5)
1 0
input 3)
5 1 2 3 4
output 3)
5 1 2 3 4 (1 2 3 4 5)
1 2 0
input 4)
3 1 2 5 4
output 4)
3 1 2 5 4 (1 2 3 4 5)
2 1 2 4 0
input 5)
4 2 5 1 7 6 3
output 5)
4 2 5 1 7 6 3 (1 2 3 4 5 6 7)
3 1 6 2 6 3 6 4 0
input 6)
3 6 1 2 6
output 6)
3 6 1 2 6 (1 2 3 6 6)
4 2 4 0
구현방법
코드에 있는 주석으로 대체.. 배고파.. 쓸 힘이 없다... 먹고 수정하겠지
코드
#include <stdio.h>
int n;
int pancake[30];
int sorted[60]; // 출력할 상태를 저장
int sort_point = 0;
int border; // pivot 역할
int find_max(int border){
int max = 0; // max의 인덱스를 반환한다
for (int i = 0; i < border; i++) {
if (pancake[max] <= pancake[i]) max = i;
}
return max;
}
void filp(int a) {
int temp[30] = { 0, };
for (int i = 0; i<=a; i++) {
temp[i] = pancake[a-i];
}
for (int i = 0; i <=a; i++) {
pancake[i] = temp[i];
}
}
int is_sorted(int n) {
// 정렬된 상태이면 1 반환
for (int i = 1; i < n;i++) {
if (pancake[i-1] > pancake[i]) return 0;
}
return 1;
}
int is_rightPlace(int now) {
// 처음부터 now까지 now보다 큰 값이 있는지 확인하기
// .. 뒤에 있는 값이 자기보다 큰지도 확인하기
// 없으면 filp 안해도 됨 -> 1 반환하기
for (int i = 0; i < now; i++) {
if (pancake[i] > pancake[now]) return 0;
}
for (int i = now+1; i < border; i++) {
if (pancake[now] > pancake[i]) return 0;
}
return 1;
}
int main() {
scanf("%d", &n);
// EOF를 입력받을때까지 입력을 받는 대신 일단 n개의 입력을 받기로 함
for (int i = 0; i < n; i++) {
scanf("%d", &pancake[i]);
}
for (int i = 0; i < n;i++) {
printf("%d ", pancake[i]);
}
if (is_sorted(n) == 1) {
printf("\n0");
return 0;
}
border = n; // pivot 역할
int cnt = 0;
while (is_sorted(border) != 1) {
int max_idx = find_max(border);
// max 인덱스가 border와 같으면 -> border --;
// -> 입력이 30개까지, 10 이하의 수만 등장하므로 중복일 수 있어 이 가능성은 채택되지 않음
// -> 대신 filp을 여러번 할 수 있음(제 자리에 있음에도 불구하고)
// -> 그럼 제자리에 있는지 확인하면 되는거 아닌가~
// -> is_rightPlace 함수 만듦
//
// max 인덱스가 첫번째에 있으면 -> filp(border) -> border--;
// max 인덱스가 다른 곳에 있으면 -> filp(max_idx) -> border--;
if (max_idx == 0) {
sorted[sort_point] = 1 + cnt;
sort_point++
filp(border-1);
}
else if (is_rightPlace(max_idx) != 1 && max_idx != border-1) {
sorted[sort_point] = n - max_idx;
sort_point++;
filp(max_idx);
continue;
}
border--;
cnt++; // border가 감소한 횟수 측정
}
if (is_sorted(n) == 1) {
printf("(");
for (int i = 0; i < n; i++) {
if (i == n - 1) printf("%d", pancake[i]);
else printf("%d ", pancake[i]);
}
printf(")\n");
for (int i = 0; i <= sort_point; i++) {
printf("%d ", sorted[i]);
}
return 0;
}
}
리뷰..를 가장한 아무말
- 오랜만에 문제 풀이를 써서 그런지 잘 전달이 되는지 모르겠다 ..
- 문제 푸는데 시간도 오래 걸리고 사소한 부분에 자꾸 걸려 고칠 때마다 막막했는데 풀고나니 너무 뿌듯했다 ㅠㅜㅠㅜ 지피티도 안쓰고 ,, 대견해 나 자신 ,,
- 반례가 될 만한 테스트 케이스 찾는 것도 일이었다 .. 새로운 거 넣어볼 때마다 무서웠음
- 갈 길이 멀다 ... 열심히 배워야지~
++ 유사한 백준 문제도 풀었다~!! 첫 골드문제를 풀다니 감격...🥹
