개발 블로그

문제 링크  : www.acmicpc.net/problem/16935

문제

크기가 N×M인 배열이 있을 때, 배열에 연산을 R번 적용하려고 한다. 연산은 총 6가지가 있다.

1번 연산은 배열을 상하 반전시키는 연산이다.

2번 연산은 배열을 좌우 반전시키는 연산이다.

3번 연산은 오른쪽으로 90도 회전시키는 연산이다.

4번 연산은 왼쪽으로 90도 회전시키는 연산이다.

5번 연산은 1번 그룹의 부분 배열을 2번 그룹 위치로, 2번을 3번으로, 3번을 4번으로, 4번을 1번으로 이동시키는 연산이다.

6번 연산은 1번 그룹의 부분 배열을 4번 그룹 위치로, 4번을 3번으로, 3번을 2번으로, 2번을 1번으로 이동시키는 연산이다.

입력

첫째 줄에 배열의 크기 N, M과 수행해야 하는 연산의 수 R이 주어진다.

둘째 줄부터 N개의 줄에 배열 A의 원소 Aij가 주어진다.

마지막 줄에는 수행해야 하는 연산이 주어진다. 연산은 공백으로 구분되어져 있고, 문제에서 설명한 연산 번호이며, 순서대로 적용시켜야 한다.

출력

입력으로 주어진 배열에 R개의 연산을 순서대로 수행한 결과를 출력한다.

제한

• 2 ≤ N, M ≤ 100
• 1 ≤ R ≤ 1,000
• N, M은 짝수
• 1 ≤ Aij ≤ 108

접근 방법

이전에 풀었던 배열 돌리기 1,2 번 문제와는 달리 약간 노가다로 푸는 문제였다.

배열의 인덱스만 주의해주면 쉽게 해결할 수 있다.

연산을 여러번 수행하는 경우도 있으므로 초기화에 주의해야하며, 90도 회전시 가로/세로 가 서로 바뀐다는 것도 고려해야한다.

또한 연산 번호를 입력받을 때 공백을 포함해서 받아야하는데 이때 주의할 점이 있다.

getline(cin, remainder)에서 개행문자(\n)를 받아줘야하는 것이다. 

그래야 getline(cin, strNum)에 정상적으로 "1 2 3 4 5  6"이 들어가는 것이다. 

만약 getline(cin, remainder) 처리를 안 해주면,

배열의 마지막 원소를 입력하고 친 엔터를 strNum에 받아서 strNum = "\n"만 들어가고 끝난다.

(cin 은 엔터 무시하는데 getline은 엔터 무시 안함.)

//21.03.10
//연산 끝나고 초기화 주의
//getline 개행문자까지 입력받는 점 주의!! (remainder 로 버퍼에 있는 엔터 처리)

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

#define MAX 101
using namespace std;

int map[101][101];
int map2[101][101];
int N,M,R;

void print(){
    for(int i = 0; i<N; i++){
        for(int j = 0; j<M; j++){
            printf("%d ", map[i][j]);
        }printf("\n");
    }
    printf("\n");
}

void init1(){
    
    for(int i = 0; i<MAX; i++){
        for(int j = 0; j<MAX; j++){
            map[i][j] = 0;
        }
    }
}
void init2(){
    
    for(int i = 0; i<MAX; i++){
        for(int j = 0; j<MAX; j++){
            map2[i][j] = 0;
        }
    }
}


//상하 반전
void func1(){
    
    int tmp;
    for(int i = 0; i<N/2; i++){
        for(int j = 0; j<M; j++){
            tmp= map[N-1-i][j];
            map[N-1-i][j] = map[i][j];
            map[i][j] = tmp;
        }
    }

}

void func2(){
    int tmp;
    
    for(int i = 0; i<N; i++){
        for(int j=0; j<M/2; j++){
            tmp = map[i][M-1-j];
            map[i][M-1-j] = map[i][j];
            map[i][j] = tmp;
        }
    }

}

void func3(){
    
    for(int i = 0; i<N; i++){
        for(int j = 0; j<M; j++){
            map2[j][N-1-i] = map[i][j];
        }
    }
    init1();
    for(int i = 0; i<M; i++){
        for(int j = 0; j<N; j++){
            map[i][j] = map2[i][j];
        }
    }
    int tmp = N;
    N = M;
    M = tmp;
    
}

void func4(){
    
    for(int i = 0; i<N; i++){
        for(int j = 0; j<M; j++){
            map2[M-1-j][i] = map[i][j];
        }
    }
    init1();
    for(int i = 0; i<M; i++){
        for(int j = 0; j<N; j++){
            map[i][j] = map2[i][j];
        }
    }
    int tmp = N;
    N = M;
    M = tmp;
}

void func5(){
        
    //첫번째 그룹 임시저장
    for(int i = 0; i<N/2; i++){
        for(int j = 0; j<M/2; j++){
            map2[i][j] = map[i][j];
        }
    }
    //4->1
    for(int i = 0; i<N/2; i++){
        for(int j = 0; j<M/2; j++){
            map[i][j] = map[i+N/2][j];
        }
    }
    //3->4
    for(int i = N/2; i<N; i++){
        for(int j = 0; j<M/2; j++){
            map[i][j] = map[i][j+M/2];
        }
    }
    //2->3
    for(int i = N/2; i<N; i++){
        for(int j = M/2; j<M; j++){
            map[i][j] = map[i-N/2][j];
        }
    }
    //2->1
    for(int i=0; i<N/2; i++){
        for(int j = M/2; j<M; j++){
            map[i][j] = map2[i][j-M/2];
        }
    }
    init2();
    
    
}
void func6(){
    //첫번째 그룹 임시저장
    for(int i = 0; i<N/2; i++){
        for(int j = 0; j<M/2; j++){
            map2[i][j] = map[i][j];
        }
    }
    //2->1
    for(int i = 0; i<N/2; i++){
        for(int j = 0; j<M/2; j++){
            map[i][j] = map[i][j+M/2];
        }
    }
    //3->2
    for(int i = 0; i<N/2; i++){
        for(int j = M/2; j<M; j++){
            map[i][j] = map[i+N/2][j];
        }
    }
    //4->3
    for(int i = N/2; i<N; i++){
        for(int j = M/2; j<M; j++){
            map[i][j] = map[i][j-M/2];
        }
    }
    //4->1
    for(int i=N/2; i<N; i++){
        for(int j = 0; j<M/2; j++){
            map[i][j] = map2[i-N/2][j];
        }
    }
    init2();
}



int main(){
    
    cin >> N >> M >> R;
        
    for(int i = 0; i<N; i++){
        for(int j = 0; j<M; j++){
            cin >> map[i][j];
        }
    }
 
    
    vector<int> numVec;
    string remainder; getline(cin, remainder);
    string strNum;
    getline(cin, strNum);
    
    for(int i = 0; i<strNum.length(); i++){
        if(i%2 == 0) numVec.push_back(strNum[i]-'0');
    }
    
    for(int i = 0; i<numVec.size(); i++){
        int num = numVec[i];
        init2();
        switch(num){
               case 1:
                   func1();
                   break;
               case 2:
                   func2();
                   break;
               case 3:
                   func3();
                   break;
               case 4:
                   func4();
                   break;
               case 5:
                   func5();
                   break;
               case 6:
                   func6();
                   break;
               deafult:
                   break;
           }
        //print();
    }
    
     for(int i = 0; i<N; i++){
         for(int j = 0; j<M; j++){
             printf("%d ", map[i][j]);
         }printf("\n");
     }
    
    
    return 0;
}

문제 링크 : www.acmicpc.net/problem/16927

문제

크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다.

예를 들어, 아래와 같은 배열을 2번 회전시키면 다음과 같이 변하게 된다.

배열과 정수 R이 주어졌을 때, 배열을 R번 회전시킨 결과를 구해보자.

입력

첫째 줄에 배열의 크기 N, M과 수행해야 하는 회전의 수 R이 주어진다.

둘째 줄부터 N개의 줄에 배열 A의 원소 Aij가 주어진다.

출력

입력으로 주어진 배열을 R번 회전시킨 결과를 출력한다.

제한

• 2 ≤ N, M ≤ 300
• 1 ≤ R ≤ 10^9
• min(N, M) mod 2 = 0
• 1 ≤ Aij ≤ 108

접근 방법

nanyoungkim.tistory.com/78

문제와 동일한데, 조건 하나가 다르다. R의 범위가 1000에서 10^9 까지 늘어났다는 것이다. 

예를 들어보자.

여기서 map[0][0]이 1번 전진하면 map[1][0]으로 간다. 그런데 1번 전진이 아니라 13번, 25번 전진해도 map[1][0]으로 간다. 

즉,

1 mod 12

13 mod 12

25 mod 12

는 모두 1임을 알 수 있는데, 여기서 modulus 12는 가장 바깥쪽 박스의 칸 수가 된다. 이는 2*N + 2*M -4 로 구할 수 있다. (-4는 각 모서리의 수들이 반복돼서 더해준 것을 뺀 것이다.)

박스가 하나씩 안 쪽으로 들어갈 때마다 가로, 세로의 길이는 각각 2씩 감소하는 것을 알 수 있다.

배열 돌리기 1번에서는 "각 박스에 대해 1칸 전진" 을 R번 반복 했다면, 

배열 돌리기 2번에서는 "박스 한개에 대해 R번 전진" 을 박스 개수만큼 반복해줬다.

결론은 박스 개수만큼 반복하는데, 한 박스마다 회전할 수를 R이 아닌 "R mod 박스칸수" 로 지정해서 R이 10^9처럼 큰 수가 들어와도 효율적으로 돌아갈 수 있게 했다.

//21.03.10
//next가 배열 범위 넘어가면 dr[],dc[]의 인덱스 증가
//top, right, bottom, left 순서로 칸 이동시킴
//(시계 반대방향으로 전진해야하므로 dr,dc의 인덱스는 오,아,왼,위 순서)

#include <iostream>
#include <algorithm>


using namespace std;

int map[301][301];
int N,M,R;

//오, 아, 왼, 위
int dr[4] = {0,1,0,-1};
int dc[4] = {1,0,-1,0};

void rotate(int start, int len){
    
    int r = R%len;			//len은 박스의 총 칸 수
    for(int i = 0; i<r; i++){   //r칸 전진
        
        int startVal = map[start][start];
        int r = start;
        int c = start;
        
        int k = 0;
        while(k<4){
            
            int nr = r + dr[k];     //map[nr][nc]는 옮길 대상임 (map[r][c]로 옮겨야 함)
            int nc = c + dc[k];
            
            if(nr==start && nc==start) break;
            if(start<=nr && nr<N-start && start<=nc && nc<M-start){
                
                //차례로 시계 반대방향으로 옮김
                map[r][c] = map[nr][nc];
                r = nr;
                c = nc;
                
            }
            else{       //다음에 옮길 칸이 배열 범위 넘어가버리면 해당 라인은 다 옮긴거라서 k 증가
                k++;
            }
        }
        map[start+1][start] = startVal; //처음에 시작지점 빼놨던거 마지막에 빈 자리에 넣어줌.
        
    }

    
}


int main(){
    
    cin >> N >> M >> R;
        
    for(int i = 0; i<N; i++){
        for(int j = 0; j<M; j++){
            cin >> map[i][j];
        }
    }
    
    int cnt = min(N,M)/2;       //  박스 수


    int n=N, m=M;
    
    for(int i = 0; i<cnt; i++){ //반복문 1번에,  박스 1개가 R만큼 전진함
            //시작 지점
        rotate(i, 2*n + 2*m -4);
        n-=2;	//박스 안으로 들어갈때마다 가로,세로 2씩 줄어듦.
        m-=2;
        
    }
    
    
    
    
    
    for(int i = 0; i<N; i++){
        for(int j = 0; j<M; j++){
            cout << map[i][j] << " ";
        }cout <<"\n";
    }
    
    
    
    return 0;
}

문제 링크 : www.acmicpc.net/problem/16926

문제

크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다.

예를 들어, 아래와 같은 배열을 2번 회전시키면 다음과 같이 변하게 된다.

배열과 정수 R이 주어졌을 때, 배열을 R번 회전시킨 결과를 구해보자.

입력

첫째 줄에 배열의 크기 N, M과 수행해야 하는 회전의 수 R이 주어진다.

둘째 줄부터 N개의 줄에 배열 A의 원소 Aij가 주어진다.

출력

입력으로 주어진 배열을 R번 회전시킨 결과를 출력한다.

제한

• 2 ≤ N, M ≤ 300
• 1 ≤ R ≤ 1,000
• min(N, M) mod 2 = 0
• 1 ≤ Aij ≤ 108

접근 방법

모든 박스에 대해서 시계 반대 방향으로 요소를 1칸씩 이동시키며, 이를 R번 반복한다.

여기서 박스는

이렇게 두개이다.

박스의 시작지점은 map[0][0] -> map[1][1] -> map[2][2]...... map[박스수][박스수] 이런 순으로 가게 된다.

박스의 개수는 min(N,M) / 2 개이며 문제의 조건에서 min(N,M) mod 2=0이라고 했으므로 둘 중하나는 짝수이고 (3x3) 이나 (5x5) 같은 경우는 고려하지 않아도 된다.

먼저 각 박스에 대해서 1칸 시계 반대방향으로 이동하는 걸 생각해보자.  1) map[0][0]을 시작지점으로 잡는다.

2) Top : 왼쪽으로 이동한다. 

next 칸이 now칸의 오른쪽에 있으므로 dr[],dc[]는 오른쪽.

3) Right : 위쪽으로 이동한다.

next 칸이 now칸의 아래쪽에 있으므로 dr[],dc[]는 아래.

4) Bottom : 오른쪽으로 이동한다.

next 칸이 now칸의 왼쪽 있으므로 dr[],dc[]는 왼쪽.

5) Left : 아래쪽으로 이동한다.

next 칸이 now칸의 위에 있으므로 dr[],dc[]는 위.

전체적인 로직은 위와 같으며, next 칸이 시작점으로 돌아왔을 때 반복을 멈추고, 남은 자리에 1)에서 저장했던 값을 넣어주면 된다.

//21.03.10
//next가 배열 범위 넘어가면 dr[],dc[]의 인덱스 증가
//top, right, bottom, left 순서로 칸 이동시킴
//(시계 반대방향으로 전진해야하므로 dr,dc의 인덱스는 오,아,왼,위 순서)

#include <iostream>
#include <algorithm>


using namespace std;

int map[301][301];
int N,M,R;

//오, 아, 왼, 위
int dr[4] = {0,1,0,-1};
int dc[4] = {1,0,-1,0};

void rotate(int box){
    
    for(int i=0; i<box; i++){   //박스수만큼 반복(1칸 전진)(시작점은 start, start+1, start+2..)
        int startVal = map[i][i];       //각 박스 시작은 [0][0] -> [1][1] -> [2][2]...
        int r = i;
        int c = i;
        
        int k = 0;
        while(k<4){
            
            int nr = r + dr[k];     //map[nr][nc]는 옮길 대상임 (map[r][c]로 옮겨야 함)
            int nc = c + dc[k];
            
            if(nr==i && nc==i) break;
            if(i<=nr && nr<N-i && i<=nc && nc<M-i){
                
                //차례로 시계 반대방향으로 옮김
                map[r][c] = map[nr][nc];
                r = nr;
                c = nc;
                
            }
            else{       //다음에 옮길 칸이 배열 범위 넘어가버리면 해당 라인은 다 옮긴거라서 k 증가
                k++;
            }
        }
        map[i+1][i] = startVal; //처음에 시작지점 빼놨던거 마지막에 빈 자리에 넣어줌.
     
    }
 
    
}


int main(){
    
    cin >> N >> M >> R;
        
    for(int i = 0; i<N; i++){
        for(int j = 0; j<M; j++){
            cin >> map[i][j];
        }
    }
    
    int cnt = min(N,M)/2;       //  박스 수
    
    for(int i = 0; i<R; i++){       //반복문 한번에 1칸 전진하는것. 총 R칸 전진
        rotate(cnt);
    }


    for(int i = 0; i<N; i++){
        for(int j = 0; j<M; j++){
            cout << map[i][j] << " ";
        }cout <<"\n";
    }
    
    
    
    return 0;
}

참고 : 4ngeunlee.tistory.com/219

문제 링크 : www.acmicpc.net/problem/16931

문제

크기가 N×M인 종이가 있고, 종이는 1×1크기의 칸으로 나누어져 있다. 이 종이의 각 칸 위에 1×1×1 크기의 정육면체를 놓아 3차원 도형을 만들었다.

종이의 각 칸에 놓인 정육면체의 개수가 주어졌을 때, 이 도형의 겉넓이를 구하는 프로그램을 작성하시오.

위의 그림은 3×3 크기의 종이 위에 정육면체를 놓은 것이고, 겉넓이는 60이다.

입력

첫째 줄에 종이의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에는 종이의 각 칸에 놓인 정육면체의 수가 주어진다.

출력

첫째 줄에 도형의 겉넓이를 출력한다.

접근 방법

각 배열 칸에 대해 옆면 4개의 겉넓이를 구하고 마지막에 위(N*M)넓이와 아래(N*M)넓이를 더해줬다.

각 배열 칸에 대한 옆면의 넓이 4개를 구하는게 관건인데, 이는 인접한 배열칸의 높이와 현재 위치칸의 높이의 차를 이용해서 구할 수 있다.

1) 현재칸 높이 >= 인접한 칸 높이 -> 가려지지 않은 부분의 높이는 (현재-인접)

2) 현재칸 높이 =< 인접한 칸 높이 -> 다 가려져 버려서 높이는 0

이때 주의할 점은 가장자리 즉 가장 바깥쪽 옆면의 넓이인데, 이는 인접한 칸의 높이가 0이라고 생각하면 된다. 

만약 N=4, M=4이면

o 표시한 곳에 입력받은 숫자를 저장하고

그 주위로는 0을 저장해서 높이를 0으로 표시하면 쉽게 계산할 수 있다.

#include <iostream>


using namespace std;

int arr[102][102];			//가장 자리 처리를 위해서 

//위 오 아 왼
int dr[4] = {-1,0,1,0};
int dc[4] = {0,1,0,-1};


int main(){
    
    int ans = 0;
    
    int N,M;
    cin>>N>>M;
    
    for(int i = 0; i<N+2; i++){		//가장 자리를 0으로 설정하기 위한 범위
        for(int j=0; j<M+2; j++){
            arr[i][j] = 0;
        }
    }
    
    for(int i = 1; i<=N; i++){			//가장 자리 빼고 안쪽에 숫자 입력 받음
        for(int j=1; j<=M; j++){
            cin>>arr[i][j];
        }
    }
    
    for(int r = 1; r<=N; r++){
        for(int c=1; c<=M; c++){
            
            for(int k = 0; k<4; k++){
                int nr = r+dr[k];
                int nc = c+dc[k];
                
                if(arr[r][c]>=arr[nr][nc]){			//현재 위치가 더 커서 위로 나올 때만 더함
                    ans+=arr[r][c] - arr[nr][nc];
                }
            }
            
            
        }
    }
    
    //위, 아래
    ans+=2*(N*M);
    cout << ans;
    
    return 0;
}