백준(10811) - 바구니 뒤집기 [C 언어]

오늘은 8달 전에 푸는 걸 실패한 후 방치해뒀던 문제를 가지고 왔다.

바로 바구니 뒤집기~ 문제를 읽어보자!

 

 

이 문제는 따로 더 배워야 하는 개념은 없지만 로직을 잘 이해해서 반복문을 잘 이용하는 것이 관건이었다.

8달 전에 틀린 이유도 이런 로직을 못 짜겠어서 포기한 것이었는데, 

그래서 이번에는 문제를 풀어보기 전, 어떻게 풀 것인지 대략적으로 그려보기로 했다.

나의 허접한 마우스그림

 

여기서 볼 것이, 역순이 되는 간격이 매번 변한다는 것이었는데, 이를 모두 포괄하도록 나의 코드를 일반화하는 것이

중요해보였다. 가능한 경우의 수를 먼저 나누어 보았다.

1. 하나만 고른 경우 

2. 짝수개 고른 경우

3. 홀수개 고른 경우

어떤 방식으로 할까 고민하다가, 역순은 중간을 기점으로 양 끝부터 두 수씩 바꾼다는 아이디어를 이용해보기로 했다. 

그래서 전체 간격을 2로 나눈 것을 반복 횟수로 한 후, 간단히 변수의 값을 서로 바꿔주는 방식으로 코드를 써보았다.

#include <stdio.h>
int main(){
    int n, m, temp, start, end;
    scanf("%d %d", &n, &m);	//1)첫쨰줄에 바구니 개수와 바꾸는 횟수 주어짐
    int bas[n];
    for(int i = 1; i <= n; i++){
        bas[i-1] = i;
    }
    for(int i = 0; i < m; i++){	//2)바꾸는 횟수만큼 반복
        scanf("%d %d", &start, &end);	//3)역순의 구간 받아오기
        start--;
        end--;
            for(int i = 0; i <=(end-start)/2; i++){	//4)구간을 2로 나눈 몫만큼 반복
                temp = bas[start + i];
                bas[start + i] = bas[end - i];
                bas[end - i] = temp;
        }
    }
    for(int i = 0; i < n; i++){
        printf("%d ", bas[i]);
    }
    return 0;
}

 

우선 제출을 누르기 전에 이렇게 하면 모든 경우의 수를  다룰 수 있는지 계산해보았다.

여기에서 알아두어야 할 점은 구간을 2로 나눈 몫은 정수로 계산 되어서 하나만 고르면 0, 홀수개를 고른 경우에는

절반보다 0.5 작은 정수로 정해진다는 것이다. 어차피 2개씩 바꾸는 것이기 때문에 홀수개를 고른 경우에 중간은

바꾸지 않아도 된다는 점을 잘 커버하는 것 같아 제출을 눌렀다.

 

결과는 맞았습니다! :)

이번 문제는 따로 더 배워야하는 어려운 문법이 없어서 바로 맞출 수 있었다.^^

앞으로는 문제를 무작정 풀기 전에 생각을 해보며 푸는 과정을 꼭 빼놓지 않고 해보는 습관을 들여야 겠다.

그럼 다음 문제에서 다시 봅시다아 - ^ㅇ^