[백준] 10811번 : 바구니 뒤집기 | C++

1. 문제 상세

 

https://www.acmicpc.net/problem/10811

 

 

 

2. 문제 접근

 

10813번 : 공 바꾸기 문제와 비슷하다.

 

크기가 100인 배열을 선언하고 해당 배열을 N 만큼만 사용하며 M번의 작업을 한다.

 

작업 전에 배열의 0 ~ N-1번 인덱스까지의 값을 모두 1 ~ N 까지의 값으로 초기화한다.

 

각 작업은 배열의 i - 1 번 인덱스의 값부터 j - 1 번 인덱스의 값을 역순으로 바꾼다.

이를 위해 for문을 사용하여 i 가 j 보다 작을 때, i 에 1을 더하고, j 에 1을 빼며 반복하도록 한다.

반복에서는 배열의 i - 1 번 인덱스의 값과 j - 1 번 인덱스의 값을 바꾼다.

 

M번의 작업 후 N크기의 배열을 출력한다.

 

 

 

3. 문제 풀이

 

#include <iostream>
using namespace std;

int main() {
    int a[100], n, m, i, j, temp;
    
    cin >> n >> m;
    
    for(int x = 0; x < n; x++) a[x] = x + 1;
    for(int x = 0; x < m; x++) {
        cin >> i >> j;
        for(; i < j; i++, j--) {
            temp = a[i - 1];
            a[i - 1] = a[j - 1];
            a[j - 1] = temp;
        }
    }
    for(int x = 0; x < n; x++) cout << a[x] << " ";
}

 

 

크기가 100인 정수형 배열 a 와 정수형 변수 n, m, i, j, temp 를 선언.

cin 으로 바구니의 갯수와 바구니를 역순으로 바꾸는 횟수를 입력받아 n 과 m 에 저장한다.

 

for문을 사용하여 x 가 0일때 부터 n 보다 작을 때 1씩 더하며 반복하도록 한다.

반복에서는 배열 a 의 x 번 인덱스의 값을 x + 1 값으로 초기화한다.

 

위 반복문이 끝나면 for문을 사용하여 x 가 0일때 부터 m 보다 작을 때 1씩 더하며 반복하도록 한다.

반복에서는 cin 으로 인덱스 두 자리를 입력받아 각각 i, j 에 저장한다.

for문을 사용하여 i 가 j 보다 작을 때, i 에는 1씩 더하고, j 에는 1씩 빼며 반복하도록 한다.

반복에서는 temp 에 배열 a 의 i - 1 번 인덱스의 값을 저장하고 i - 1 번 인덱스의 값에는 j - 1 번 인덱스의 값을 저장한다.

그리고 j - 1 번 인덱스의 값에는 temp의 값을 저장하여 i - 1 번과 j - 1 번 인덱스의 값을 교환한다.

 

위 반복문이 끝나면 for문으로 x 가 0부터 n 보다 작을 때 1씩 더하며 반복, cout 으로 배열 a 의 x 번 인덱스의 값을 출력한다.

 

 

 

4. 성능 확인

 

 

 

 

5. 마무리

 

배열의 값을 역순으로 바꾸는 알고리즘을 사용해 보았다.