[C언어] 백준 10811번 바구니 뒤집기

[ 문제 ]

도현이는 바구니를 총 N개 가지고 있고, 각각의 바구니에는 1번부터 N번까지 번호가 순서대로 적혀져 있다.

바구니는 일렬로 놓여져 있고,

가장 왼쪽 바구니를 1번째 바구니, 그 다음 바구니를 2번째 바구니, ..., 가장 오른쪽 바구니를 N번째 바구니라고 부른다. 

도현이는 앞으로 M번 바구니의 순서를 역순으로 만들려고 한다.

도현이는 한 번 순서를 역순으로 바꿀 때, 순서를 역순으로 만들 범위를 정하고,

그 범위에 들어있는 바구니의 순서를 역순으로 만든다.

바구니의 순서를 어떻게 바꿀지 주어졌을 때,

M번 바구니의 순서를 역순으로 만든 다음, 바구니에 적혀있는 번호를 가장 왼쪽 바구니부터 출력하는 프로그램을 작성하시오.

 

[ 입력 ]

첫째 줄에 N (1 ≤ N ≤ 100)과 M (1 ≤ M ≤ 100)이 주어진다.

둘째 줄부터 M개의 줄에는 바구니의 순서를 역순으로 만드는 방법이 주어진다.

방법은 i j로 나타내고, 왼쪽으로부터 i번째 바구니부터 j번째 바구니의 순서를 역순으로 만든다는 뜻이다. (1 ≤ i ≤ j ≤ N)

도현이는 입력으로 주어진 순서대로 바구니의 순서를 바꾼다.

 

 

[ 출력 ]

모든 순서를 바꾼 다음에, 가장 왼쪽에 있는 바구니부터 바구니에 적혀있는 순서를 공백으로 구분해 출력한다.

 

[ 작성한 코드 ]

#include <stdio.h>

int main(int argc, char *argv[])
{
   int N,M,i,j;
   int arr[100];
   int temp; //순서를 바꿀 때 값을 임시로 저장할 변수
   
   scanf("%d %d",&N,&M);

   for(int a = 0; a < N; a++)
   {
       arr[a] = a+1;
   }
   for(int a = 0; a < M; a++)
   {
       scanf("%d %d",&i,&j);
       for(int b = i - 1; b < j - 1; b++)
       {
           temp = arr[i-1];
           arr[i-1] = arr[j-1];
           arr[j-1] = temp;
           j--;
           i++;
       }      
   }

   for(int a = 0; a < N; a++)
   {
       printf("%d ",arr[a]);
   }

    return 0;
}

 

10813번 공 바꾸기 문제(https://www.acmicpc.net/problem/10813)와 개념이 비슷하다고 생각해서 문제를 풀 때 어려움이 없을 것 같다고 생각했는데 아니었다.

 

바구니를 역순으로 뒤집는걸 어떻게 구현해야하나 고민했는데 자리를 바꿀 때 범위내에서 바구니를 역순으로 바꿀 때 j의 값은 감소시키고 i의 값을 증가시키면 범위내의 바구니를 역순으로 배치시킬 수 있었다.

 

 

	arr[0]	arr[1]	arr[2]	arr[3]	arr[4]
	1	2	3	4	5
1  2	2	1	3	4	5
3  4	2	1	4	3	5
1  4	3	4	1	2	5
2  2	3	4	1	2	5

 

입력값이 1 4 일때 범위내의 수들이 역순으로 배치되어야하는데 i = 1, j = 4 일 때, 실제 arr[0] 에서 arr[3] 까지가 범위이므로

arr[0] 과 arr[3]의 자리를 변경하고 i++ , j-- 를 거쳐 arr[1] 과 arr[2] 자리를 변경하는 식으로 코드를 작성했다.

 

내 생각에 굳이 i++, j--를 안해도 구할 수 있는 방법이 있을 것 같은데... 조금 더 고민해보고 다시 코드를 작성하면 코드를 업데이트 해봐야겠다.

 

글을 올리고보니 굳이 i++을 사용하지 않아도된다는 사실을 알았다.

 

(변경 전)

for(int a = 0; a < M; a++)
   {
       scanf("%d %d",&i,&j);
       for(int b = i - 1; b < j - 1; b++)
       {
           temp = arr[i-1];
           arr[i-1] = arr[j-1];
           arr[j-1] = temp;
           j--;
           i++;
       }      
   }

 

(변경 후)

for(int a = 0; a < M; a++)
   {
       scanf("%d %d",&i,&j);
       for(int b = i - 1; b < j - 1; b++)
       {
           temp = arr[b];
           arr[b] = arr[j-1];
           arr[j-1] = temp;
           j--;
       }      
   }

 

이미 for문에서 b = i -1이라고 선언했으니 굳이 arr[i-1]을 사용하지 않고 arr[b]를 사용하면 i++을 사용할 필요가 없다.

 

알고리즘 분류

• 구현
• 시뮬레이션