개발 블로그

4
123 1 1
356 1 0
327 2 0
489 0 1

2

접근 방법

완전 탐색으로 접근했다. 

답이 될 수 있는 숫자 조건은 000 ~ 999 중에 아래 두 조건을 만족해야 한다.  만족하지 않으면 배열 값을 -1 로 표시한다. 

1) 모두 다른 숫자로 구성되어 있어야 함

2) 숫자에 0이 들어가면 안됨

그 후 반복문을 돌면서 스트라이크, 볼 갯수를 카운트하고

카운트 한 스트라이크, 볼 갯수가 처음에 입력한 스트라이크/볼 수와 일치하면

그 인덱스의 배열 값을 +1 한다. (ex. 처음 입력한 숫자가 123 1 1 이고, 비교 대상이 324이면 1strike, 1ball을 만족하므로 arr[324]++)

그리고 마지막에 arr[i]의 값이 N과 동일하면, 즉 N번을 물어봤기 때문에 그 물어본 횟수만큼 테스트를 통과했으면(스트라이크, 볼 갯수가 일치했으면) 그 i는 후보가 된다. 그 i가 몇개인지 카운트 하면 이 문제의 답을 구할 수 있다. 

[반례]

입력
2
123 0 0
456 0 0

정답
6

import java.util.*;

public class BOJ_2503_숫자야구 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int ans = 0;

//        Integer[] arr = new Integer[1000];
        int[] arr = new int[1000];
        for (int i = 123; i <= 987; i++) {  //서로 다른 숫자 세개로 구성하므로
            String str = Integer.toString(i);   //각 자리수 비교하기 위해 형변환

            if (str.charAt(0) == str.charAt(1) || str.charAt(0) == str.charAt(2) || str.charAt(1) == str.charAt(2)
                ||str.charAt(0)=='0' || str.charAt(1)=='0' ||str.charAt(2)=='0') {  //서로 다른 숫자로 구성되지 않았으면 -1로 지정
                arr[i] = -1;
            }
        }
        //ArrayList<String> strNumList = new ArrayList<>();
        String strNum;
        //ArrayList<Integer> strikeList = new ArrayList<>();
        //ArrayList<Integer> ballList = new ArrayList<>();
        int strike;
        int ball;
        for (int i = 1; i <= N; i++) {       //N : 민혁이가 영수에게 질문한 횟수
            strNum = sc.next();
            //strNumList.add(strNum);
            strike = sc.nextInt();
            //strikeList.add(strike);
            ball = sc.nextInt();
            //ballList.add(ball);

            int strikeCnt = 0;
            int ballCnt = 0;

            for (int idx = 123; idx <= 987; idx++) {    //반복문 돌면서 strike, ball 검사
                if (arr[idx] == -1) continue;
                //System.out.print(arr[idx] + " ");
                int passCnt = 0;
                //strike 검사
                strikeCnt = 0;
                String strIdx = Integer.toString(idx);
                for (int j = 0; j < 3; j++) {
                    if (strNum.charAt(j) == strIdx.charAt(j)) strikeCnt++;
                }

                //strike 수는 맞았으니 Ball 검사
                ballCnt = 0;
                for (int p = 0; p < 3; p++) {
                    for (int q = 0; q < 3; q++) {
                        if ((strNum.charAt(p) == strIdx.charAt(q)) && (p != q)) {
                            ballCnt++;
                        }
                    }
                }
                if ((strike != strikeCnt) || ball != ballCnt) {
                    arr[idx] = -1;
                    continue;
                }

				//통과된 횟수 카운트
                if ((strike == strikeCnt) && (ball == ballCnt)) {
                    arr[idx]++;
                }
            }

        }

        for (int i = 123; i <= 987; i++) {

            if (arr[i] != -1 && arr[i] == N) {	//물어본 횟수만큼 다 만족했으면 그 숫자는 답
                ans++;
               // System.out.println(i);
            }
        }
        System.out.println(ans);

    }
}

문제 : https://www.acmicpc.net/problem/1662

접근 방법

[처음 코드]

입력 문자열을 stack 에 push 한 뒤, 단순하게 문자열 끝(stack의 top)부터 탐색을 진행했다. 탐색을 진행할 때는 세가지 케이스를 나눴다. 먼저 그냥 숫자이면 len을 하나씩 증가시키고, ')'이면 pop 하고, '('이면 '('의 앞 숫자(k)를 len에 곱했다. 

그러나 아래 코드는 문제에서 주어진 예제는 맞췄으나, 또 다른 반례를 생각하지 못했다. 

반레 : () 안에 압축 문자열이 여러개가 포함이 될 때  -> ex. 45(12)53(52(1111)42(222)) 

import java.util.*;
public class Main {

    public static void main(String[] args) {

        String input;
        Scanner sc = new Scanner(System.in);
        input = sc.next();
        int inputLen = input.length();

        char[] arr = input.toCharArray();

        Stack<Character> stack = new Stack<Character>();
        for(int i = 0; i < inputLen; i++){
            stack.push(arr[i]);
        }

        int len = 0;
        while(!stack.empty()){
            char topChar = stack.peek();
            if(topChar == ')') {
                stack.pop();
            }
            else if(topChar == '('){
                stack.pop();
                int k = (int)stack.pop() - '0';
                len = len*k;
              
            }
            else{
                len++;
                stack.pop();
            }
        }
        System.out.println(len);
    }
}

[정답 코드]

입력 문자열을 끝이 아닌 처음부터 stack에 push 해가면서 탐색을 진행한다. 단 ')'를 만나기 전까지 탐색을 진행한다. ')'를 만나면 push 했던 문자열들을 pop 해가면서 압축 문자열을 해제하는 로직을 수행한다. 이 때 while문을 돌면서 '('를 만나기 전까지 stack에서 pop해가면서 길이를 계산한다. K(Q)의 길이를 알아냈다면, 그 길이를 다시 stack에 push하는데, 이는 하나의 괄호 쌍 안에 여러개의 압축 문자열이 있을 때를 위한 것이며, 계산한 압축 문자열의 길이와 기존에 입력 문자열을 구분하기 위해 계산한 압축 문자열의 길이를 push 할 때에는 길이를 push한 뒤에 바로 "+"를 push 해준다. 

입력 문자열의 끝까지 push하면서 탐색을 끝냈다면, stack에서 하나씩 Pop 해가면서 최종 길이를 계산한다.

*주의 :  Stack Type을 Char형으로 정의 시 형변환 하는 과정에서 오류 -> String Type으로 정의해야한다.

import java.util.*;
import java.io.*;
public class BOJ1662_압축 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] arr = br.readLine().split("");

        Stack<String> stack = new Stack<String>();
        for(int i = 0; i < arr.length; i++){

            if(!arr[i].equals(")")) {stack.push(arr[i]);}
            else {
                int cnt = 0;
                while (!stack.peek().equals("(")) {
                    String topStr = stack.pop();
                    if (topStr.equals("+")) {
                        int len = Integer.parseInt(stack.pop());
                        cnt += len;
                    } else cnt++;
                }
                stack.pop(); // ( 제거
                int k = Integer.parseInt(stack.pop());
                cnt = cnt * k;
                stack.push(String.valueOf(cnt));
                stack.push("+");
            }
     }
        int answer = 0;
        while(!stack.empty()){
            if(stack.peek().equals("+")){
                stack.pop();
                //System.out.println(stack.peek());
                answer += Integer.parseInt(stack.pop());
            }
            else{
                stack.pop();
                answer++;
            }
        }
        System.out.println(answer);
    }
}

참고 : https://codeung.tistory.com/256

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

문제

M줄 N칸으로 되어 있는 표 위에, 달팽이 모양으로 선을 그리려고 한다.

위의 그림은 M=5, N=3의 예이다. 이제 표의 왼쪽 위 칸(ㅇ)에서 시작하여, 오른쪽으로 선을 그려 나간다. 표의 바깥 또는 이미 그려진 칸에 닿아서 더 이상 이동할 수 없게 되면, 시계방향으로 선을 꺾어서 그려나간다.

위의 표는 선을 그려 나간 모양을 나타낸 것이다. 선이 꺾어진 부분은 대각선으로 나타내었다. 표의 모든 칸이 채워질 때까지, 선을 몇 번 꺾게 될까?

입력

첫째 줄에 M과 N이 빈 칸을 사이에 두고 주어진다. (2 ≤ M, N ≤ 100)

출력

첫째 줄에 표의 모든 칸이 채워질 때까지 선이 꺾어지는 횟수를 출력한다.

접근 방법

시작 지점 [0][0]에서 시작해서 오, 아, 왼, 위 방향 순으로 전진하며, 

이미 map[nr][nc]가 1이거나(방문 먼저 했거나) 범위 넘어가면 카운트를 증가한다.

M*N 만큼 칸을 방문하면 반복문을 멈춘다.

//
//  SM_BOJ1952_달팽이2.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/05/01. 4:46 ~ 
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

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

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

int main(){
    
    int M, N;
    cin >> M >> N;
    
    memset(map, 0, sizeof(map));
    int ans = 0;
    int cnt = 1;
    
    int d= 0;
    int r = 0;
    int c = 0;
    map[r][c] = 1;
    while(1){
        
        if(cnt== M*N) break;
          
        int nr = r + dr[d];
        int nc = c + dc[d];
        
        //범위 넘어가거나 이미 map[i][j]==1 이면
        if(nr<0 || nr>M-1 || nc<0 || nc>N-1 || map[nr][nc]==1){
            ans += 1;
            if(d==3) d = 0;
            else d = d+1;
        }
        else{
            map[nr][nc] = 1;
            cnt += 1;
            r = nr;
            c = nc;
        }
    }
    cout << ans; 
    
    
    
    return 0;
}

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

문제

홀수인 자연수 N이 주어지면, 다음과 같이 1부터 N2까지의 자연수를 달팽이 모양으로 N×N의 표에 채울 수 있다.

N이 주어졌을 때, 이러한 표를 출력하는 프로그램을 작성하시오. 또한 N2 이하의 자연수가 하나 주어졌을 때, 그 좌표도 함께 출력하시오. 예를 들어 N=5인 경우 6의 좌표는 (4,3)이다.

입력

첫째 줄에 홀수인 자연수 N(3 ≤ N ≤ 999)이 주어진다. 둘째 줄에는 위치를 찾고자 하는 N2 이하의 자연수가 하나 주어진다.

출력

N개의 줄에 걸쳐 표를 출력한다. 각 줄에 N개의 자연수를 한 칸씩 띄어서 출력하면 되며, 자릿수를 맞출 필요가 없다. N+1번째 줄에는 입력받은 자연수의 좌표를 나타내는 두 정수를 한 칸 띄어서 출력한다.

접근 방법

1) N에 따른 회오리 수를 구해준다. (N/2번)

2) 각 회오리마다 시작 지점의 행과 열을 지정한다. (N/2 -1, N/2 -1)

3) 방향을 나타내는 배열 dr[4], dc[4]의 방향을 오, 아, 왼, 위  순서로 지정한다.

4) 시작 지점에서 전진을 하면서 숫자를 하나씩 증가시키며 이차원 배열을 채워 넣고, 일정 범위를 넘어가면 전진 방향을 바꾼다.

5) 이때 범위는 몇번째 회오리인지에 따라 달라지는데, 회오리가 i 번째라고 하면 행과 열의 범위는 N/2-i ~ N/2+i 가 된다.

회오리 하나의 칸을 다 채웠으면 다음 바깥쪽의 회오리를 채우며, 다음 회오리로 넘어갈 때 시작 지점을 행-1, 열-1 로 지정한다.

//
//  SM_BOJ1913_ 달팽이.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/05/01.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//


#include <iostream>
#include <utility>

using namespace std;

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

int map[1000][1000];
int main(){
    
    pair<int,int> p;
    
    int N, x;
    cin >> N >> x;
    
    int rotateCnt = N/2;        //회오리 수
        
    int num = 1;
    map[N/2][N/2] = num;
    
    int startR = N/2 -1;
    int startC = N/2 -1;
    for(int i = 1; i<=rotateCnt; i++){
        
        int r = startR;
        int c = startC;
        
        for(int d = 0; d<4;){
            int nr = r + dr[d];
            int nc = c + dc[d];
            
            if((N/2 -i<=nr && nr<=N/2+i) && (N/2 -i<=nc && nc<=N/2+i)){
                num+=1;
                map[nr][nc] = num;
                if(num==x){
                    p.first = nr + 1;
                    p.second = nc + 1;
                }
                r = nr; //다음 칸 전진
                c = nc;
            }
            else{   //범위 넘어갔으니 방향 바꿔야함
                d++;
            }
           
        }
          
        //시작점 바꾸기 -1, -1
        startR -= 1;
        startC -= 1;
        
    }
    
    for(int i = 0; i<N; i++){
        for(int j = 0; j<N; j++){
            cout << map[i][j] << " ";
        }cout << endl;
    }
    cout << p.first << " " << p.second ;
    
    
    
    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;
}