개발 블로그

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

문제

나3곱2 게임은 정수 하나를 이용한다. 가장 먼저, 정수 x로 시작하고, 연산을 N-1번 적용한다. 적용할 수 있는 연산은 두 가지 있고, 아래와 같다.

• 나3: x를 3으로 나눈다. x는 3으로 나누어 떨어져야 한다.
• 곱2: x에 2를 곱한다.

나3곱2 게임을 진행하면서, 만든 수를 모두 기록하면 수열 A를 만들 수 있다. 예를 들어, x = 9, N = 6이고, 적용한 연산이 곱2, 곱2, 나3, 곱2, 나3인 경우에 A = [9, 18, 36, 12, 24, 8] 이다.

수열 A의 순서를 섞은 수열 B가 주어졌을 때, 수열 A를 구해보자.

입력

첫째 줄에 수열의 크기 N(2 ≤ N ≤ 100)이 주어진다. 둘째 줄에는 수열 B가 주어진다. B에 포함된 원소는 1018 보다 작거나 같은 자연수이다.

출력

나3곱2 게임의 결과 수열 A를 출력한다. 항상 정답이 존재하는 경우에만 입력으로 주어지며, 가능한 정답이 여러가지인 경우에는 아무거나 출력한다.

접근 방법

주의할 점 : B에 포함된 원소는 10^18 보다 작거나 같은 자연수이므로 자료형을 long long 으로 해줘야 한다. int 형으로 하면 출력초과나 틀렸습니다가 나온다. 

주어진 조건대로 직관적으로 풀어보았다.

1. 주어진 수열 B의 첫번째 요소를 x로 설정한다.

1-1. x곱2 연산을 한 결과가 (수열 B에 있고 x로 설정한 적이 없으면) 수열 A에 push 하고 DFS를 호출한다. 

1-2. x곱2 연산을 한 결과가 (수열 B에 없거나 x로 설정한 적이 있으면) 나3 연산을 진행한다.

     1-2-1) x가 3의 배수이고, x/3이 수열 A에 있고 ,x/3을 x로 설정한 적이 없으면 수열 A에 x/3을 push 하고 DFS를 호출한다. 

이 과정을 반복해서 수열 A의 크기가 N이 되면 DFS를 빠져나갈 때 바로 빠져나가기 위해 iscontinue를 false로 설정한 뒤 수열 A의 원소를 출력한다. 

예로 A = {4 8 6 3 12 9} 이고 x=4로 설정한 후 실행했다고 해보자.

4*2 = 8 -> 8은 수열 A에 존재하고 x=4이므로 visited한 적 없으므로 수열A에 8을 push하고 DFS를 호출한다. 

8*2 = 16은 수열 A에 존재하지 않으므로 16을 수열 A에서 pop 하고 DFS를 빠져나간다.

다시 8에 대해 나3 연산을 수행해본다. 8은 3의 배수가 아니므로 수열 A에서 8을 pop하고 DFS를 빠져나간다. 

다시 4에 대해 나3연산을 수행해본다. 4도 3의 배수가 아니므로 수열 A에서 8을 pop하고 DFS를 빠져나간다. 

이제 x=8로 설정하고 위와 같이 반복한다.

//
//  BF_BOJ16936_나3곱2.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/04/03.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
#include <vector>
#include <utility>

using namespace std;

vector<long long> vecB;
vector<long long> vecA;
int visited[100] = {0};
int N;

pair<bool, int> isIn(long long num){					
    for(int i = 0; i<N; i++){
        if(vecB[i]==num) return make_pair(true, i);		//<해당 숫자가 있는지,수열 B에서 몇번째 인덱스인지>
    }
    return make_pair(false, -1);
}

bool iscontinue = true;
void DFS(long long x, int cnt){
    
    if(cnt==N){
        iscontinue = false;
        for(int i = 0; i<N; i++){
            cout << vecA[i] << " ";
        }
        printf("\n");
        return;
    }
    
    //곱2
    pair<bool, int> p = isIn(2*x);
    if(p.first==true && visited[p.second]==0){
        visited[p.second] = 1;
        vecA.push_back(x*2);
        DFS(x*2, cnt+1);
        if(iscontinue){
            vecA.pop_back();
            visited[p.second] = 0;
        }else return;
       
    }

    
    //나3
    if(x%3 == 0){
        pair<bool, int> p2 = isIn(x/3);
        if(p2.first==false) return;
        else if(p2.first==true && visited[p2.second]==0){
            visited[p2.second] = 1;
            vecA.push_back(x/3);
            DFS(x/3, cnt+1);
            if(iscontinue){
                vecA.pop_back();
                visited[p2.second] = 0;
            }else return;
           
        }
    }
    
    if(iscontinue==false) return;
}


int main(){

    cin>>N;
   
    long long num;
    for(int i = 0; i<N; i++){
        scanf("%lld", &num);
        vecB.push_back(num);
    }
    
    for(int i = 0; i<vecB.size(); i++){			//주어진 수열 B에서 하나씩 x로 지정해서 DFS 돌림
        visited[i] = 1;
        vecA.push_back(vecB[i]);
        DFS(vecB[i], 1);
        if(iscontinue==true){					//수열 A 찾지 못했을 경우 pop 하고 다음 요소를 x로 지정해서 반복
            vecA.pop_back();
            visited[i] = 0;
        }else break;
    }
    
    return 0;
}

아래의 방법은 velog.io/@hschoi1104/BOJ-16936-%EB%82%983%EA%B3%B12

를 참고해서 위의 코드를 수정한 것이다. 

//
//  BF_BOJ16936_나3곱2.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/04/03.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

vector<long long> vecB;
vector<long long> vecA;
int N;


void DFS(long long x, int cnt){

    if(cnt==N){
        for(int i = 0; i<N; i++){
            cout << vecA[i] << " ";
        }
        exit(0);
    }
    

    if(x%3==0 && find(vecB.begin(), vecB.end(), x/3)!=vecB.end()){
        vecA.push_back(x/3);
        DFS(x/3, cnt+1);
        vecA.pop_back();
    }
    if(find(vecB.begin(), vecB.end(), 2*x)!=vecB.end()){
        vecA.push_back(2*x);
        DFS(2*x, cnt+1);
        vecA.pop_back();
    }
    return;
}


int main(){

    cin>>N;
   
    long long num;
    for(int i = 0; i<N; i++){
        scanf("%lld", &num);
        vecB.push_back(num);
    }
    
    for(int i = 0; i<vecB.size(); i++){
       
        vecA.push_back(vecB[i]);
        DFS(vecB[i], 1);
        vecA.pop_back();
            
    }
    
    return 0;
}

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

문제

로마 숫자에서는 수를 나타내기 위해서 I, V, X, L을 사용한다. 각 문자는 1, 5, 10, 50을 의미하고, 이 문제에서 다른 문자는 사용하지 않는다.

하나 또는 그 이상의 문자를 이용해서 수를 나타낼 수 있다. 문자열이 나타내는 값은, 각 문자가 의미하는 수를 모두 합한 값이다. 예를 들어, XXXV는 35, IXI는 12를 의미한다.

실제 로마 숫자에서는 문자의 순서가 중요하지만, 이 문제에서는 순서는 신경쓰지 않는다. 예를 들어, 실제 로마 숫자에서 IX는 9를 의미하지만, 이 문제에서는 11을 의미한다.

로마 숫자를 N개 사용해서 만들 수 있는 서로 다른 수의 개수를 구해보자.

입력

첫째 줄에 사용할 수 있는 문자의 개수 N (1 ≤ N ≤ 20)이 주어진다.

출력

첫째 줄에 로마 숫자 N개를 사용해서 만들 수 있는 서로 다른 수의 개수를 출력한다.

접근 방법

완전탐색 문제라 모든 경우의 수에 대해 DFS 로 풀었는데 시간 초과가 떴다.

문제의 조건에서 순서를 상관하지 않으므로 IIX = XII 이다. 이는 중복 조합으로 해결할 수 있다.

중복조합은 서로 다른 n개 중 k 개를 뽑는 경우인데, 여기서는 서로 다른 4개(I,V,X,L) 개 중 중복을 허용하고 순서 상관 없이 N개를 뽑는것이다.

DFS() 안의 반복문을 보자.

시작 값을 변화시킴으로써 중복 조합을 구현할 수 있다. i의 변화 값은 다음과 같다. (4개만 나타냄)

(앞에 -가 붙은 경우는 시작 값을 i=0으로 고정시켰을 경우에 나오는 경우이다. 시작 값을 변화시킴으로써 IIX = XII 처럼 같은 수를 나타내는 경우 한번만 카운트 할 수 있다.)

0 0 0 0

0 0 0 1

0 0 0 2

0 0 0 3

- 0 0 1 0

0 0 1 1

0 0 1 2

0 0 1 3

- 0 0 2 0

- 0 0 2 1

0 0 2 2

0 0 2 3

- 0 0 3 0

- 0 0 3 1

- 0 0 3 2

0 0 3 3

...

//
//  BF_BOJ16922_로마숫자만들기.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/04/03.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

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

using namespace std;

#define I 1
#define V 5
#define X 10
#define L 50

int N;
int answer = 0;
int sum = 0;
bool visited[1001] = {0};
char cArr[4] = {'I','V','X','L'};
int iArr[4] = {1,5,10,50};

vector<int> sumVec;
vector<string> strVec;
string str = "";
void pickDFS(int toPick, int start, int s){
    
    
    if(toPick==0){
        if(visited[s]==false){
            answer++;
            visited[s]=true;
        }
        return;
    }
    
    for(int i = start; i<4; i++){				//시작점을 바꿔서 중복 조합 구현 가능
        pickDFS(toPick-1, i, s+iArr[i]);
    }
    
}


int main(){
    cin>>N;
    pickDFS(N, 0, 0);
    cout << answer;
    
    return 0;
}

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

문제

현진 치킨에서 판매하는 치킨은 양념 치킨, 후라이드 치킨, 반반 치킨으로 총 세 종류이다. 반반 치킨은 절반은 양념 치킨, 절반은 후라이드 치킨으로 이루어져있다. 양념 치킨 한 마리의 가격은 A원, 후라이드 치킨 한 마리의 가격은 B원, 반반 치킨 한 마리의 가격은 C원이다.

상도는 오늘 파티를 위해 양념 치킨 최소 X마리, 후라이드 치킨 최소 Y마리를 구매하려고 한다. 반반 치킨을 두 마리 구입해 양념 치킨 하나와 후라이드 치킨 하나를 만드는 방법도 가능하다. 상도가 치킨을 구매하는 금액의 최솟값을 구해보자.

입력

첫째 줄에 다섯 정수 A, B, C, X, Y가 주어진다.

출력

양념 치킨 최소 X마리, 후라이드 치킨 최소 Y마리를 구매하는 비용의 최솟값을 출력한다.

접근 방법

X,Y가 구입하는 "최소" 개수라는 것을 주의해야한다. 즉 최소 가격이기만 하면 추가로 더 구매할 수 있다는 것이다. (단 max(X,Y) 보다 많이 구매한다면 최소 가격이 될 수 없음)

양념, 후라이드 각각 구매하는 것 보다 반반을 두마리 구매하는게 더 싸며 X>Y 라고 가정해보자. 

그럼 아래의 1) ~ 2) 사이에서 반반으로 얼마만큼 구매하느냐에 따라 가격이 달라지며, 반복문을 돌면서 최소 가격을 구한다. 

1) Y마리는 반반으로 구매하고,  (X-Y) 마리는 후라이드 치킨 따로 구매.

2) X마리 전부 반반으로 구매

//
//  BF_BOJ16917_양념반후라이드반.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/04/03.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//
//X,Y가 구입하는 "최소" 개수라는 것을 주의해야한다.
//즉, X,Y 개 이상 구입할 수 있는 것이다.
//반복문을 돌면서 반반으로 얼마나 구매해야하는지와 그때의 최소 가격을 구한다.

#include <iostream>
using namespace std;

int main(){

    int A,B,C,X,Y;
    cin >> A >> B >> C >> X >> Y;
    
    
    bool ischeapBanBan = A+B>2*C ? true : false;    //양념 + 후라이드 각각 사는게 더 싼지 체크
    
    long long mini = 10000000000, sum;
    if(ischeapBanBan){
        
        if(X>Y) {
           
            for(int i = Y; i<=X; i++){
                sum = 2*C*i + (X-i)*A;          //(X-i) : 반반 구매하고 더 구매해야 하는 양념 치킨 수
                if(sum<mini) {mini = sum;}
            }
        }
        else {
            for(int i = X; i<=Y; i++){
                sum = 2*C*i + (Y-i)*B;         //(Y-i) : 반반 구매하고 더 구매해야 하는 후라이드 치킨 수
                if(sum<mini) {mini = sum;}
            }
        }
        
    }
    else{
        mini  = A*X + B*Y;
    }
    
    cout << mini;
    return 0;
}

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

문제

상도시의 차량 번호판 형식이 주어졌을 때, 가능한 차량 번호판의 개수를 구해보자.

• 번호판에 사용할 수 있는 숫자는 0, 1, 2, ..., 8, 9이다.
• 사용할 수 있는 문자는 a, b, c, d, ..., y, z이다.
• 차량 번호판의 형식은 최대 4글자이고, c와 d로 이루어진 문자열로 나타낼 수 있다.
• c는 문자가 위치하는 자리, d는 숫자가 위치하는 자리이다.
• 같은 문자 또는 숫자가 연속해서 2번 나타나면 안 된다.

예를 들어, 형식이 "cd"이면, a1, d4, h5, k4 등이 가능하다. 형식이 "dd"인 경우에 01, 10, 34, 69는 가능하지만, 00, 11, 55, 66은 같은 숫자가 2번 연속해서 불가능하다.

입력

첫째 줄에 차량 번호판의 형식이 주어진다. 형식은 길이가 4보다 작거나 같으며, c와 d로만 이루어져 있다.

출력

첫째 줄에 가능한 차량 번호판의 개수를 출력한다.

접근 방법

완전탐색 문제로 모든 경우의 수를 다 구해주면 된다.

형식을 string 으로 입력받고, 첫 글자 type[0]에 따라 answer 값 초기 설정을 해준다. 

그 후 type[1] 부터 반복문을 돌면서 이전 형식과 일치하는지(연속하는지) 검사하면서 경우의 수를 곱해나간다. 연속하는 경우는 문자일 경우 26-1개를 곱하고, 숫자일 경우 10-1개를 곱한다. 

//
//  BF_BOJ16968_차량번호판1.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/04/03.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//
//완전탐색
//이전과 형식 연속되는지만 체크해서 연속되면 해당 글자와 겹치지 않게 1 감소시켜서 곱하기


#include <iostream>
#include <string>

using namespace std;


int main(){
    
    string type;
    cin >> type;
    int answer;
    
    int numD = 10;      //0~9
    int numC = 26;      //a~z
    
    if(type[0]=='c') answer = numC;
    else answer = numD;
    
    for(int i = 1; i<type.length(); i++){       //이전 형식과 연속되는지 검사
        
        if(type[i]=='c'){
            
            if(type[i-1]=='c'){ //연속된 경우 cc
                answer *= (numC-1);
            }
            else{   //dc
                answer *= numC;
            }
        }
            
        else{
            
            if(type[i-1]=='c'){ //cd
                answer *= numD;
            }
            else{   //연속된 경우 dd
                answer *= (numD-1);
            }
        }
        
    }
    
    cout << answer;
    
    
    
    
    return 0;
}

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

문제

N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.

아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.

아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.

아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.

• 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
• 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
• 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
  • 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
  • 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

아기 상어의 이동은 1초 걸리고, 물고기를 먹는데 걸리는 시간은 없다고 가정한다. 즉, 아기 상어가 먹을 수 있는 물고기가 있는 칸으로 이동했다면, 이동과 동시에 물고기를 먹는다. 물고기를 먹으면, 그 칸은 빈 칸이 된다.

아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.

공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 공간의 크기 N(2 ≤ N ≤ 20)이 주어진다.

둘째 줄부터 N개의 줄에 공간의 상태가 주어진다. 공간의 상태는 0, 1, 2, 3, 4, 5, 6, 9로 이루어져 있고, 아래와 같은 의미를 가진다.

• 0: 빈 칸
• 1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
• 9: 아기 상어의 위치

아기 상어는 공간에 한 마리 있다.

출력

첫째 줄에 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다.

접근 방법

fishVec에 pair를 활용해 <거리, 행, 열>  정보 담은 후 sort함수 이용해 정렬하면 자동으로 우선순위가 적용되는 점을 이용했다.

물고기를 한 마리 먹을 때마다 현재 위치에서 BFS함수 돌려서 먹을 수 있는 물고기들을 fishVec에 넣는다. 그 후 sort로 정렬해서 가장 앞의 물고기 먹고 위치와 아기상어 크기 등 조건들을 조정해준다.

fishVec에 물고기가 없으면 더 이상 먹을 물고기가 없는 것이므로 while(1)을 종료한다.

주의할 점은 맨 처음 아기상어의 위치를 입력받아서 다른 변수에 저장한 후 해당 칸 0으로 설정해야하는 점이다. 아기상어의 현재 위치가 계속 바뀌므로 처음 위치를 빈칸으로 바꿔줘야한다.

sort() 활용 전에 노가다로 하다가 시간초과가 났는데 sort() 를 활용하니 코드와 조건식이 간단해져서 시간 안에 해결할 수 있었다.

//
//  SM_BOJ16236_아기상어.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/03/25.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

//fishVec에 거리, 행, 열 정보 담아서 sort함수 이용해 정렬하면 자동으로 우선순위 적용됨
//물고기 한 마리 먹을 때마다 현재 위치에서 BFS함수 돌려서 먹을 수 있는 물고기들 fishVec에 넣고 sort 후 가장 앞의 물고기 먹고 위치 조정
//fishVec에 물고기 없으면 종료
//맨 처음 아기상어의 위치 저장 후 해당 칸 0으로 설정해서 빈칸으로 바꿔줘야함. (아기상어의 현재 위치 바뀌므로)

#include <iostream>
#include <queue>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

int N;
int map[20][20];

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


int nowR, nowC;
int babySize = 2;
int toEat = 2;
int resSec = 0;

vector<pair<pair<int,int>,int>> fishVec;        //거리, 가장 위쪽, 가장 왼쪽


void BFS(int row, int col){ //현재 위치에서 먹을 수 있는 물고기까지의 거리와 위치 저장
    
    fishVec.clear();                //현재 위치 바뀌었으므로, 벡터 비운 후 바뀐 현재위치 중심으로 가장 가까운 물고기들 push
    queue<pair<int,int>> que;
    que.push(make_pair(row,col));       //다음에 어디 방문할지 저장하는 큐
    
    int fromStart[20][20] = {0};
    int visited[20][20] = {0};
    visited[row][col] = 1;      //현재 위치는 이미 방문함
    
    int minDist = 1000;
    
    while(!que.empty()){
        
        int r = que.front().first;
        int c = que.front().second;
        que.pop();
        
        for(int i = 0; i<4; i++){
            int nr = r + dr[i];
            int nc = c + dc[i];
            
            if(nr<0 || nr>=N || nc<0 || nc>=N || visited[nr][nc]==1 || babySize<map[nr][nc]) continue;  //범위 넘어가거나, 방문했거나, 크기 크면 못 지나감
            
            fromStart[nr][nc] = fromStart[r][c] + 1;
            visited[nr][nc] = 1;
            que.push(make_pair(nr,nc));
            
            if(map[nr][nc]>0 && babySize>map[nr][nc]){  //먹을 수 있는 물고기 (작은거)
                
                //먹을 수 있는 물고기 중 가장 가까운 물고기 먹기
                if(minDist>=fromStart[nr][nc]){
                    minDist = fromStart[nr][nc];
                    fishVec.push_back(make_pair(make_pair(minDist, nr),nc));
                    
                   // cout << nr << " " << nc << "  거리 : " << minDist << "\n";
                }
            }
        }
    }
}


int main(){
    

    cin >> N;
    for(int i = 0; i<N; i++){
        for(int j = 0; j<N; j++){
            scanf("%d", &map[i][j]);
            if(map[i][j] == 9) {
                map[i][j] = 0;
                nowR = i; nowC = j;}    //아기상어 위치 저장
        }
    }
    
    
    while(1){
        
        
        BFS(nowR, nowC);            //현재 위치에서 가장 가까운 물고기들 탐색
        if(fishVec.size()==0){      //먹을 수 있는 물고기 없을 때까지
            
            break;
        }
        else{
            
            sort(fishVec.begin(), fishVec.end());   //거리 같은 물고기들 중 위/ 왼 우선순위 적용해서 정렬 후 가장 앞의 요소 먹기
            
            resSec += fishVec[0].first.first;       //이동거리 = 걸린 초
            
            
            //잡아 먹음
            toEat-=1;
            if(toEat==0){
                babySize+=1;
                toEat = babySize;
            }
            
            
            //잡아먹었으니 아기상어 위치 바뀜
            nowR = fishVec[0].first.second;
            nowC = fishVec[0].second;
            
            map[nowR][nowC] = 0;        //해당 칸 물고기 없어져서 빈칸됨
            
        }
    }
    cout <<resSec;
    
    
    
    return 0;
}

참고 : rile1036.tistory.com/90

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

문제

크기가 H × W인 배열 A와 두 정수 X와 Y가 있을 때, 크기가 (H + X) × (W + Y)인 배열 B는 배열 A와 배열 A를 아래로 X칸, 오른쪽으로 Y칸 이동시킨 배열을 겹쳐 만들 수 있다. 수가 겹쳐지면 수가 합쳐진다.

즉, 배열 B의 (i, j)에 들어있는 값은 아래 3개 중 하나이다.

• (i, j)가 두 배열 모두에 포함되지 않으면, Bi,j = 0이다.
• (i, j)가 두 배열 모두에 포함되면, Bi,j = Ai,j + Ai-X,j-Y이다.
• (i, j)가 두 배열 중 하나에 포함되면, Bi,j = Ai,j 또는 Ai-X,j-Y이다.

배열 B와 정수 X, Y가 주어졌을 때, 배열 A를 구해보자.

입력

첫째 줄에 네 정수 H, W, X, Y가 주어진다. 둘째 줄부터 H + X개의 줄에 배열 B의 원소가 주어진다.

항상 배열 A가 존재하는 경우만 입력으로 주어진다.

출력

총 H개의 줄에 배열 A의 원소를 출력한다.

제한

• 2 ≤ H, W ≤ 300
• 1 ≤ X < H
• 1 ≤ Y < W
• 0 ≤ Bi,j ≤ 1,000

접근 방법

프로그램이 시작하면 arrB에 입력을 받고 그 중 (H x W) 만큼만 map배열에 옮긴다. 

그 후, 행은 X부터 H+X 까지 / 열은 Y부터 W+Y까지 돌면서 즉, 배열 A끼리 겹치는 부분에 한해서 요소끼리 뺄셈 연산을 해준다. (겹친 부분 처리)

이때 주의할 점은 A에서 A를 빼야하고, 뺀 결과를 즉시 반영해 배열 값을 갱신하면서 매 행을 진행해나가야 한다는 것이다. 

아래의 예를 들어서 설명해보겠다.

입력이 다음과 같이 주어졌다고 하자.

3 4 1 1
1 2 3 4 0
5 7 9 11 4
9 15 17 19 8
0 9 10 11 12

그럼 배열 B는 아래와 같다.

아래 배열은 map 배열로, (H x W) 만큼 배열 B에서 복사해온것이다. (H x W)만큼을 제외한 곳은 0으로 채웠다.

X=1, Y=1이므로 색으로 표시한 곳이 겹치는 부분이다. 

우리는 배열 A를 쉽게 알 수 있는데, 이 배열 A를 이용해서 거꾸로 생각해보면 코드를 쉽게 구현할 수 있다. 배열 A는 아래와 같다.

이걸 X=1, Y=1만큼 옮겨서 겹친 것을 구현해보면, 다음과 같다. 

매 행을 진행해 나가면서 겹친 부분끼리 뺀 값을 갱신해줘야, 다음 행을 계산할 때 그 값이 반영돼서 올바른 값이 나온다.

다시 말하면, map[1][1]에서 map[1-X][1-Y]를 빼서 map[1][1]을 6으로 갱신해줘야, 그 다음 행의 map[2][2]-map[2-X][2-Y]를 계산할 때 올바르게 11에서 6을 뺄 수 있다. (매 행마다 값을 갱신해주지 않으면 11에서 (6+1) 을 뺀 것으로 계산된다.)

문제에서 주어진 예제로만 생각했을 때는 

for(int row = X; row<=rowB; row++){
        bool chk=false;
        for(int col = Y; col<=colB; col++){
            if(map[row][col] != 0){
                map[row][col] -= map[row-X][col-Y];
                chk = true;
            }
        }
        
        if(!chk) break;
    }

이 코드에서 map[row][col] -= arrB[row-X][col-Y]로 계산해도 결과값이 잘 나와서 어디가 틀린줄 몰랐는데,

배열 A끼리 겹친것이므로 겹친 부분에 대해서는 배열 A끼리 빼줘야하는걸 놓쳐서 틀린것이었다. 

//
//  SM_BOJ16976_배열 복원하기.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/03/25.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>

using namespace std;

int arrB[610][610];
int map[610][610];

int H,W,X,Y;

int main(){
    
    cin >> H >> W  >> X >> Y;
    int rowB = H+X;
    int colB = W+Y;
    
    for(int i = 0; i<rowB; i++){
        for(int j = 0; j<colB; j++){
            scanf("%d", &arrB[i][j]);
            map[i][j]= 0;
        }
    }
    
    for(int i = 0; i<H; i++){
        for(int j = 0; j<W; j++){
            map[i][j] = arrB[i][j];
        }
    }
    
    
    for(int row = X; row<=rowB; row++){
        bool chk=false;
        for(int col = Y; col<=colB; col++){
            if(map[row][col] != 0){
                map[row][col] -= map[row-X][col-Y];
                chk = true;
            }
        }
        
        if(!chk) break;
    }

    
    for(int i = 0; i<H; i++){
        for(int j = 0; j<W; j++){
            printf("%d ", map[i][j]);
        }
        printf("\n");
    }
    

    return 0;
}

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

문제

길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부터 2N까지의 번호가 매겨져 있다.

벨트가 한 칸 회전하면 1번부터 2N-1번까지의 칸은 다음 번호의 칸이 있는 위치로 이동하고, 2N번 칸은 1번 칸의 위치로 이동한다. i번 칸의 내구도는 Ai이다. 위의 그림에서 1번 칸이 있는 위치를 "올라가는 위치", N번 칸이 있는 위치를 "내려가는 위치"라고 한다.

컨베이어 벨트에 박스 모양 로봇을 하나씩 올리려고 한다. 로봇은 올라가는 위치에만 땅에서 올라가고, 내려가는 위치에서만 땅으로 내려갈 수 있다. 내려가는 위치에 로봇이 있는 경우 로봇은 반드시 땅으로 내려가야 한다. 로봇이 어떤 칸에 올라가거나 이동하면 그 칸의 내구도는 즉시 1만큼 감소한다. 내구도가 0인 칸에는 로봇이 올라갈 수 없다.

로봇은 컨베이어 벨트 위에서 스스로 이동할 수 있다.

컨베이어 벨트를 이용해 로봇들을 건너편으로 옮기려고 한다. 로봇을 옮기는 과정에서는 아래와 같은 일이 순서대로 일어난다.

1. 벨트가 한 칸 회전한다.
2. 가장 먼저 벨트에 올라간 로봇부터, 벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동한다. 만약 이동할 수 없다면 가만히 있는다.
   1. 로봇이 이동하기 위해서는 이동하려는 칸에 로봇이 없으며, 그 칸의 내구도가 1 이상 남아 있어야 한다.
3. 올라가는 위치에 로봇이 없다면 로봇을 하나 올린다.
4. 내구도가 0인 칸의 개수가 K개 이상이라면 과정을 종료한다. 그렇지 않다면 1번으로 돌아간다.

종료되었을 때 몇 번째 단계가 진행 중이었는지 구해보자. 가장 처음 수행되는 단계는 1번째 단계이다.

입력

첫째 줄에 N, K가 주어진다. 둘째 줄에는 A1, A2, ..., A2N이 주어진다.

출력

몇 번째 단계가 진행 중일때 종료되었는지 출력한다.

제한

• 2 ≤ N ≤ 100
• 1 ≤ K ≤ 2N
• 1 ≤ Ai ≤ 1,000

접근 방법

문제에서 주어진 조건대로만 잘 구현하면 되는 문제이다.

beltArr[1]에 로봇이 들어오고 beltArr[N]에서 로봇이 나가는 것에 유의하자.

내구도는 beltArr[1] ~ beltArr[2N] 에서 숫자가 돌고, 

로봇은 isRobot[1] ~ isRobot[N] 에서만 도는 것도 주의해야한다.

(처음에 로봇도 1부터 2N까지 돌려서 계속 헤맸었다.)

나머지는 주석을 참고하면 된다.

#include <iostream>
#include <utility>

using namespace std;

int beltArr[201] = {0};
pair<int,bool> isRobot[101]; //몇번째인지, 로봇 있는지여부
int N,K;

bool cntZero(){			//내구도 0인 곳이 K개 이상이면 true 리턴
    
    int cnt = 0;
    bool res = false;
    for(int i = 1; i<=2*N; i++){
        if(beltArr[i]==0){
            cnt++;
        }
        if(cnt>=K) {
            res = true;
            break;
        }
    }
    return res;
    
}

int findFirstRobot(){		//1~N 칸에서 가장 먼저 들어간 로봇 찾기
    
    for(int i = N; i>=1; i--){
        if(isRobot[i].second==true){
            return i;
        }
    }
    return 0;
}

//2번 : 로봇 한칸 전진 : 먼저 올라간 로봇부터 / 이동 가능하면(로봇 없고, 내구도 1이상) / 로봇&내구도 바꿈
void shiftRobot(){
    
    
    int minIdx = findFirstRobot();

    if(minIdx!=0){
        for(int i = minIdx; i>=1; i--){
            if(isRobot[i].second==true){    //현재 자리에 로봇이 있고
                
                if(i==N){					//마지막 로봇은 그냥 내림
                    isRobot[i].first = 0;
                    isRobot[i].second = false;
                }
                else{
                    if(isRobot[i+1].second==false && beltArr[i+1]>=1){  //다음 자리에 로봇 없고, 내구도 1 이상이면
                        isRobot[i+1] = isRobot[i];	//다음 칸으로 옮기고
                        beltArr[i+1] -= 1;
                        isRobot[i].first = 0;		//옮겼으니까 초기화
                        isRobot[i].second = false;
                    }
                }
                
            }
        }
    }
    
}
//1번 : 회전 : 내구도 & 로봇 위치 shift
void shiftNumber(){
    
    //내구도 이동
    int tmp = beltArr[2*N];
    for(int i = 2*N -1; i>=1; i--){
        beltArr[i+1] = beltArr[i];
    }
    beltArr[1] = tmp;
    
    
    //로봇 이동
    //내리는 위치의 로봇 처리
    isRobot[N].first = 0;
    isRobot[N].second = false;
    
    for(int i = N-1; i>=1; i--){
        isRobot[i+1] = isRobot[i];
    }
    isRobot[1].first=0;
    isRobot[1].second = false;
    
}

//3번 : beltArr[1]에 로봇없으면 로봇 하나 올림
bool putRobot(int order){
    
    if(beltArr[1]>=1 && isRobot[1].second==false) {	//처음칸의 내구도 1 이상이고 로봇 없으면
        beltArr[1]-=1;  //내구도 1 감소
        
        isRobot[1].first = order;
        isRobot[1].second = true;
        return true;
    }
    return false;
}

int solution(){
    
    int ord = 1;
    int step = 1;
    while(1){
        
        //한칸회전
        
        shiftNumber();
        if(cntZero()){break;}
        
        
        //먼저 올라간 로봇부터 전진
        shiftRobot();

        if(cntZero()){break;}
        
        //1번 비었으면 로봇 올림
        if(putRobot(ord)){		//로봇 올릴 수 있었으면 ord++
            ord++;
        }
        
        if(cntZero()){break;}
        step+=1;
    }
    
    return step; 
}

int main(){
    
    
    cin>>N>>K;
    
    for(int i = 1; i<=N; i++){
        scanf("%d", &beltArr[i]);
        isRobot[i].first = 0;
        isRobot[i].second = false;
    }
    for(int i = N+1; i<=2*N; i++){
        scanf("%d", &beltArr[i]);
    }
    
    cout << solution();
    
    return 0;
}

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

문제

드래곤 커브는 다음과 같은 세 가지 속성으로 이루어져 있으며, 이차원 좌표 평면 위에서 정의된다. 좌표 평면의 x축은 → 방향, y축은 ↓ 방향이다.

1. 시작 점
2. 시작 방향
3. 세대

0세대 드래곤 커브는 아래 그림과 같은 길이가 1인 선분이다. 아래 그림은 (0, 0)에서 시작하고, 시작 방향은 오른쪽인 0세대 드래곤 커브이다.

1세대 드래곤 커브는 0세대 드래곤 커브를 끝 점을 기준으로 시계 방향으로 90도 회전시킨 다음 0세대 드래곤 커브의 끝 점에 붙인 것이다. 끝 점이란 시작 점에서 선분을 타고 이동했을 때, 가장 먼 거리에 있는 점을 의미한다.

2세대 드래곤 커브도 1세대를 만든 방법을 이용해서 만들 수 있다. (파란색 선분은 새로 추가된 선분을 나타낸다)

3세대 드래곤 커브도 2세대 드래곤 커브를 이용해 만들 수 있다. 아래 그림은 3세대 드래곤 커브이다.

즉, K(K > 1)세대 드래곤 커브는 K-1세대 드래곤 커브를 끝 점을 기준으로 90도 시계 방향 회전 시킨 다음, 그것을 끝 점에 붙인 것이다.

크기가 100×100인 격자 위에 드래곤 커브가 N개 있다. 이때, 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 정사각형의 개수를 구하는 프로그램을 작성하시오. 격자의 좌표는 (x, y)로 나타내며, 0 ≤ x ≤ 100, 0 ≤ y ≤ 100만 유효한 좌표이다.

입력

첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커브의 시작 점, d는 시작 방향, g는 세대이다. (0 ≤ x, y ≤ 100, 0 ≤ d ≤ 3, 0 ≤ g ≤ 10)

입력으로 주어지는 드래곤 커브는 격자 밖으로 벗어나지 않는다. 드래곤 커브는 서로 겹칠 수 있다.

방향은 0, 1, 2, 3 중 하나이고, 다음을 의미한다.

• 0: x좌표가 증가하는 방향 (→)
• 1: y좌표가 감소하는 방향 (↑)
• 2: x좌표가 감소하는 방향 (←)
• 3: y좌표가 증가하는 방향 (↓)

접근 방법 

(0,0) -> (1,0) / 오(d = 0)

(0,0) -> (1,0) / 오(d=0) -> (1,-1) / 위(d=1) 

(0,0) -> (1,0) / 오(d=0) -> (1,-1) / 위(d=1) -> (0,-1) / 왼(d=2) -> (0,-2) / 위(d = 1)

이때 d의 변화를 잘 보면 가운데를 중심으로 (왼쪽d + 1) % 4 가 오른쪽 d인 것을 알 수 있다.

즉, 예시를 들면 아래와 같다.

0, 1, 2, 1에서

(0+1) % 4 = 1

(1+1) % 4 = 2

//
//  SM_BOJ15685_드래곤커브.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/03/21.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
#include <stack>
#include <utility>

using namespace std;

#define MAX 100
int map[MAX+1][MAX+1];

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

//정사각형 네꼭지점 검사
bool chkFour(int r, int c){
    if(map[r][c] && map[r][c+1] && map[r+1][c] && map[r+1][c+1]) return true;
    else return false;
}

//스택 카피 함수
stack<int> copyFunc(stack<int> stk){
    
    stack<int> tmp, res;
    while(!stk.empty()){
        tmp.push(stk.top());
        stk.pop();
    }
    
    while(!tmp.empty()){
        res.push(tmp.top());
        tmp.pop();
    }
    return res;
}


int main(){
    
    for(int i = 0; i<=MAX; i++){
        for(int j = 0; j<=MAX; j++){
            map[i][j] = 0;
        }
    }
    
    
    int N; cin >> N;
    
    int x, y, d ,g, row, col, nextR, nextC, nextD;
    for(int i = 0; i<N; i++){
        
        stack<int> stkD;
        
        cin >> x >> y >> d >> g;
        map[y][x] = 1;
        //0세대
        nextR = y + dr[d];
        nextC = x + dc[d];
        map[nextR][nextC]  = 1;
        stkD.push(d);
        
        row = nextR;
        col = nextC;
        
        //1세대 ~ g세대
        for(int i = 1; i<=g; i++){
            
            stack<int> copyStkD = copyFunc(stkD);
            
            while(!stkD.empty()){
                
                nextD = (stkD.top()+1) % 4;		//핵심 규칙
                copyStkD.push(nextD);
                stkD.pop();
                
                nextR = row + dr[nextD];
                nextC = col + dc[nextD];
                map[nextR][nextC] = 1;
                
                row = nextR;
                col = nextC;
                
            }
            stkD = copyFunc(copyStkD);
        }
        
        
        
    }
    
    int ans = 0;
    for(int i = 0; i<MAX; i++){
        for(int j = 0; j<MAX; j++){
            if(chkFour(i,j)) ans++;
        }
    }
    
    cout << ans;
    
    
    
    
    
    return 0;
}