개발 블로그

문제 링크 : https://www.acmicpc.net/problem/16953

문제

정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.

• 2를 곱한다.
• 1을 수의 가장 오른쪽에 추가한다. 

A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

입력

첫째 줄에 A, B (1 ≤ A < B ≤ 10^9)가 주어진다.

출력

A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.

접근 방법

- BFS를 이용한 완전탐색 문제이며, 자료형에 주의해야하는 문제이다.

- 주어진 입력 값 범위가 1부터 10^9 (십억)인데, 두번째 연산을 할 때 int형 범위가 넘어가므로 a, b 모두 long 형으로 선언해줘야함에 주의하자! 

- 두개의 연산 모두 원래의 값보다 증가하는 연산이므로, 연산 후 결과 값이 b를 넘어가면 que에 담지 않는다. 

#include <iostream>
#include <queue>
#include <utility>
using namespace std;

int main()
{

    long a, b;
    cin >> a >> b;

    queue<pair<long, long>> que;
    que.push(make_pair(a, 0));
    long answer = 0;

    bool flag = false;
    while (!que.empty())
    {

        long num = que.front().first;
        long cnt = que.front().second;
        que.pop();

        if (num == b)
        {
            answer = cnt;
            flag = true;
            break;
        }
        
        if(num*2 <= b){
            que.push(make_pair(num * 2, cnt + 1));
        }
        if (num * 10 + 1 <= b){
            que.push(make_pair(num * 10 + 1, cnt + 1));
        }

            
    }

    if (flag)
        cout << answer + 1;
    else
        cout << -1;
}

문제 링크  : 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;
}