[C++] 백준 16926 : 배열 돌리기 1

문제

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

 

 

 

풀이

(0,0) -> (1,1) -> (2,2) -> ... -> (b,b) 까지 각 줄을 규칙대로 이동시킨다. (<- for 문 이용하여 구현함)

1. 윗 줄을 왼쪽으로 이동
2. 왼쪽 줄을 아래로 이동
3. 맨 아래쪽 줄을 오른쪽으로 이동
4. 오른쪽 줄을 위쪽으로 이동

 

이때 b = min(n,m) / 2 로 계산된다.

 

 

코드

#include <iostream>
#include <math.h>
using namespace std;

int n, m, r;
int a[300][300];
int ans[300][300];

void turn(){
    int b = min(n,m) / 2; 
    
    for(int i=0,j=0; i<b,j<b; i++,j++){
        
        // 윗 줄을 왼쪽으로 이동
        for(int x = m-j; x >= j+1; x--){
            ans[i][x-1] = a[i][x];
        }
        
        // 왼쪽 줄을 아래로 이동
        for(int y = i; y<n-i-1; y++){
            ans[y+1][j] = a[y][j];
        }
        
        // 맨 아래쪽 줄을 오른쪽으로 이동
        for(int x = j; x<m-j-1; x++){
            ans[n-i-1][x+1] = a[n-i-1][x];
        }
        
        // 오른쪽 줄을 위로 이동
        for(int y = n-i-1; y>=i+1; y--){
            ans[y-1][m-j-1] = a[y][m-j-1];
        }
        
    }
    
    
    // 원본 배열에 결과 저장
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            a[i][j] = ans[i][j];
        }
    }
}

int main()
{
    cin >> n >> m >> r;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> a[i][j];
        }
    }
    
    //int cnt = r % ((n-1 + m-1) *2); // 회전시켜야 하는 횟수 <- 틀렸다.
    int cnt = r;

    for(int i=0; i<cnt; i++){
        turn();
    }
    
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cout << a[i][j]<<" ";
        }
        cout << "\n";
    }

    return 0;
}

 

 

 

메모

 정말 쌩 구현 문제였던 것 같다. 구현이 생각보다 쉽지 않았고, 특히 index를 고려할 때 실수하기 쉬웠던 것 같다. ㅜㅜ 

(메모장으로 정리하는데~~ 막 어지러웠다~~ ㅜㅜ ^^;;)

 

  그리고 나의 경우 예를 들어 100번 회전시킨 것과 4번 회전시킨 결과가 같은 경우를 고려해서 회전 횟수를 줄여보려고 시도했는데, 이 경우 틀렸다고 뜬다.

(0,0) 에서 옮겨야 하는 원소의 수, (1,1)에서 옮겨야 하는 원소의 수~ 이것이 경우에 따라  결론적으로 공배수 단위가 될 수도 있고, 안될 수도 있다. 그래서 원래 int cnt = r % ((n-1 + m-1) *2); 로 회전 횟수를 줄여보려고 했지만, 틀렸다는 결과가 나왔다. 실제로 찾아낸 대부분의 테스트 케이스에서 정상적으로 작동하는 것이 확인되었기 때문에 더욱 어디가 틀렸는지를 찾기가 어려웠다. 하지만 cnt를 입력받은 r 그대로 이용했을 떄에는 맞았다고 뜨는 것을 확인할 수 있었다.

 

 

시간 초과가 날까 걱정되어서 cnt 수를 줄여보려 했던 것인데, 이 경우 오히려 틀린 결과가 나올 수 있다는 점을 간과했다. 좀 더 여러 상황을 생각해보고 이런 시도를 해보면 좋을 것 같고, 일단 시간 초과가 날까 염려 정도가 되는 것이라면 그냥 제출해본 후 시간초과가 났을 때 어떻게 해결할지 고민해보는 것도 좋겠다. (확실하진 않은 경우에)