728x90
728x90

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

 

2290번: LCD Test

첫째 줄에 두 개의 정수 s와 n이 들어온다. (1 ≤ s ≤ 10, 0 ≤ n ≤ 9,999,999,999)이다. n은 LCD 모니터에 나타내야 할 수 이며, s는 크기이다.

www.acmicpc.net

 

 

문제

지민이는 새로운 컴퓨터를 샀다. 하지만 새로운 컴퓨터에 사은품으로 온 LC-디스플레이 모니터가 잘 안나오는 것이다. 지민이의 친한 친구인 지환이는 지민이의 새로운 모니터를 위해 테스트 할 수 있는 프로그램을 만들기로 하였다.

입력

첫째 줄에 두 개의 정수 s와 n이 들어온다. (1 ≤ s ≤ 10, 0 ≤ n ≤ 9,999,999,999)이다. n은 LCD 모니터에 나타내야 할 수 이며, s는 크기이다.

출력

길이가 s인 '-'와 '|'를 이용해서 출력해야 한다. 각 숫자는 모두 s+2의 가로와 2s+3의 세로로 이루어 진다. 나머지는 공백으로 채워야 한다. 각 숫자의 사이에는 공백이 한 칸 있어야 한다.

 

 


 

접근 방법

숫자 n을 가로로 분할해서 생각해보았다.

예를들어 123을 출력한다고 가정하고 s = 2라고 하자. 그러면 숫자 높이는 7이 될 것이다. 

 

즉, 숫자를 가로로 7분할 한다고 생각해보면, 아래와 같이 나타낼 수 있다.

 

123의 첫번째 라인

123의 두번째 라인

...

123의 여섯번째 라인

123의 일곱번째 라인

 

또한 LCD 특성에 맞게 숫자를 만들기 위한 가로줄의 경우가 총 5가지 경우로 한정되어 있으므로 중복코드를 피하기 위해 아래 코드와 같이 함수를 따로 작성해주었다. (space, horizon, verRight, verLeft, verBoth)

//
//  SM_BOJ2290_LCD Test.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/03/21.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>

using namespace std;

void printSpace(int s){     //가로 길이 s+2, 공백만 출력
    for(int i = 0; i<s+2; i++){ printf(" "); }
}
void printHorizon(int s){   //가로 길이 s+2, 양 옆만 공백, 가운데는 -로 채움
    printf(" ");
    for(int i = 0; i<s; i++){printf("-");}
    printf(" ");
}

void printVerRight(int s){  //가로 길이 s+2, 오른쪽 마지막에 |출력
    for(int i = 0; i<s+1; i++){printf(" ");}
    printf("|");
}
void printVerLeft(int s){   //가로 길이 s+2, 왼쪽 처음에 |출력
    printf("|");
    for(int i = 0; i<s+1; i++){printf(" ");}
}
void printVerBoth(int s){   //양쪽 공백, 가운데 s만큼 |
    printf("|");
    for(int i = 0; i<s; i++){printf(" ");}
    printf("|");
}


void printOne(int s, int row){
    
    if(row==1 || row==s+2 || row==2*s+3){ printSpace(s); }
    else{ printVerRight(s);}
}
void printTwo(int s, int row){
    if(row==1 || row==s+2 || row==2*s+3){ printHorizon(s); }
    else if(2<=row && row<=s+1){ printVerRight(s); }
    else{ printVerLeft(s);}
}
void printThree(int s, int row){
    if(row==1 || row==s+2 || row==2*s+3){ printHorizon(s);}
    else{ printVerRight(s); }
}
void printFour(int s, int row){
    if(row==1 || row==2*s+3){ printSpace(s);}
    else if(row==s+2){ printHorizon(s); }
    else if(2<=row && row<=s+1){ printVerBoth(s); }
    else{ printVerRight(s); }
}
void printFive(int s, int row){
    if(row==1 || row==s+2 || row==2*s+3){ printHorizon(s); }
    else if(2<=row && row<=s+1){ printVerLeft(s); }
    else{ printVerRight(s); }
}
void printSix(int s, int row){
    if(row==1 || row==s+2 || row==2*s+3){ printHorizon(s); }
    else if(2<=row && row<=s+1){ printVerLeft(s); }
    else{ printVerBoth(s); }
}
void printSeven(int s, int row){
    if(row==1){ printHorizon(s); }
    else if(row==s+2 || row==2*s+3){ printSpace(s); }
    else{  printVerRight(s); }
}
void printEight(int s, int row){
    if(row==1 || row==s+2 || row==2*s+3){ printHorizon(s); }
    else{ printVerBoth(s); }
}
void printNine(int s, int row){
    if(row==1 || row==s+2 || row==2*s+3){ printHorizon(s); }
    else if(2<=row && row<=s+1){ printVerBoth(s); }
    else{ printVerRight(s); }
}
void printZero(int s, int row){
    if(row==1 || row==2*s+3){ printHorizon(s); }
    else if(row==s+2){ printSpace(s); }
    else{ printVerBoth(s); }
}

int main(){
    
    int s,n;
    cin >> s >> n;
    int height = 2*s + 3;
    
    string N = to_string(n);
    
    for(int row=1; row<=height; row++){
        for(int i = 0; i<N.length(); i++){
        
            if(N[i]=='1'){ printOne(s, row); }
            else if(N[i]=='2'){ printTwo(s, row); }
            else if(N[i]=='3'){ printThree(s, row); }
            else if(N[i]=='4'){ printFour(s, row); }
            else if(N[i]=='5'){ printFive(s, row); }
            else if(N[i]=='6'){ printSix(s, row); }
            else if(N[i]=='7'){ printSeven(s, row); }
            else if(N[i]=='8'){ printEight(s, row); }
            else if(N[i]=='9'){ printNine(s, row); }
            else if(N[i]=='0'){ printZero(s, row); }
            
            printf(" ");
        }
        printf("\n");
    }

    return 0;
}

728x90
728x90

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

 

14503번: 로봇 청소기

로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어

www.acmicpc.net

 

 

문제

로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.

로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다.

로봇 청소기는 다음과 같이 작동한다.

  1. 현재 위치를 청소한다.
  2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.
    1. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
    2. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
    3. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
    4. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.

로봇 청소기는 이미 청소되어있는 칸을 또 청소하지 않으며, 벽을 통과할 수 없다.

입력

첫째 줄에 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 50)

둘째 줄에 로봇 청소기가 있는 칸의 좌표 (r, c)와 바라보는 방향 d가 주어진다. d가 0인 경우에는 북쪽을, 1인 경우에는 동쪽을, 2인 경우에는 남쪽을, 3인 경우에는 서쪽을 바라보고 있는 것이다.

셋째 줄부터 N개의 줄에 장소의 상태가 북쪽부터 남쪽 순서대로, 각 줄은 서쪽부터 동쪽 순서대로 주어진다. 빈 칸은 0, 벽은 1로 주어진다. 지도의 첫 행, 마지막 행, 첫 열, 마지막 열에 있는 모든 칸은 벽이다.

로봇 청소기가 있는 칸의 상태는 항상 빈 칸이다.

출력

로봇 청소기가 청소하는 칸의 개수를 출력한다.

 

 

 


접근 방법

로봇청소기가 움직이는 규칙을 먼저 잘 이해해야 구현하는데에 헷갈리지 않는다.

규칙을 간단히 해보면 아래와 같다. 

 

"현재 위치에서 DFS를 돌면서 네 방향 청소를 해 나가고, 네방향 청소가 다 끝나면(벽이거나 다 했거나) 뒤로 후진한다. 후진하려하는데 벽이면 종료한다."

 

문제의 예제입력2에 대해, 로봇청소기가 청소한 자리 (r,c) 와 이때까지 청소한 칸의 합을 프린트해보면 아래와 같다.

 

(7, 4)  /   1

(7, 3)  /   2

(8, 3)  /   3

(8, 4)  /   4

(9, 4)  /   5

(9, 5)  /   6

(8, 5)  /   7

(7, 5)  /   8

(6, 5)  /   9

(6, 4)  /   10

(5, 4)  /   11

(5, 3)  /   12

(6, 3)  /   13

(6, 2)  /   14

(7, 2)  /   15

(7, 1)  /   16

(8, 1)  /   17

(8, 2)  /   18

(9, 2)  /   19

(9, 3)  /   20

(9, 1)  /   21

(9, 6)  /   22

(9, 7)  /   23

(9, 8)  /   24

(8, 8)  /   25

(7, 8)  /   26

(6, 8)  /   27

(5, 8)  /   28

(5, 7)  /   29

(4, 7)  /   30

(4, 6)  /   31

(5, 6)  /   32

(5, 5)  /   33

(4, 5)  /   34

(4, 4)  /   35

(3, 5)  /   36

(3, 6)  /   37

(3, 7)  /   38

(3, 8)  /   39

(2, 8)  /   40

(1, 8)  /   41

(1, 7)  /   42

(1, 6)  /   43

(1, 5)  /   44

(1, 4)  /   45

(1, 3)  /   46

(2, 3)  /   47

(2, 2)  /   48

(3, 2)  /   49

(3, 1)  /   50

(4, 1)  /   51

(5, 1)  /   52

(5, 2)  /   53

(6, 1)  /   54

(2, 1)  /   55

(1, 1)  /   56

(1, 2)  /   57

 

청소기의 이동 흔적을 그림으로 나타내보았다. (초록, 분홍, 파랑, 노랑 순서)

 

 

//
//  SM_BOJ14503_로봇청소기.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/03/21.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>

using namespace std;

int map[50][50];
int visited[50][50];
int N, M;

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

void dfs(int r, int c, int d, int sum){ //2번
    
//    1. 현재 위치를 청소한다.
//    2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.
//    a.왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
//    b.왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
//    c.네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
//    d.네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.
    
    
    for(int i = 0; i<4; i++){       //왼쪽부터 반시계방향
        
        int nd = (d+3-i)%4;
        int nr = r + dr[nd];
        int nc = c + dc[nd];
        
        if(nr<0 || nr>=N || nc<0 || nc>=M || map[nr][nc]==1) {  //범위 넘어가거나 벽이면 다음 방향
            continue;
        }
        
        //a.  아직 청소하지 않은 공간이 존재한다면
        if(visited[nr][nc] == 0 && map[nr][nc] == 0){
               visited[nr][nc] = 1; //현재 위치 청소
               dfs(nr, nc, nd, sum+1);
           }

    }
    

    int backIdx = d+2<4 ? d+2 : d-2;
    int backr = r + dr[backIdx];
    int backc = c + dc[backIdx];
    if(0<=backr && backr<=N && 0<=backc && backc<=M){
        if(map[backr][backc]==0){   //뒤쪽 방햑 벽 아니어서 후진할 수 있을 때
            dfs(backr, backc, d, sum);  //한칸 후진
        }
        else{   //뒤쪽 방향 벽이라 후진 못할 때
            cout << sum <<endl;
            exit(0);
        }
    }
      
}



int main(){
    
    int r, c, d;
    cin >> N >> M;
    cin >> r >> c >> d;
    
    for(int i = 0; i<N; i++){
        for(int j = 0; j<M; j++){
            cin >>map[i][j];
            visited[i][j] = 0;
        }
    }
    
    visited[r][c] = 1;
    dfs(r,c,d,1);

    return 0;
}

728x90
728x90

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

 

14890번: 경사로

첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다.

www.acmicpc.net

 

 

문제

크기가 N×N인 지도가 있다. 지도의 각 칸에는 그 곳의 높이가 적혀져 있다. 

오늘은 이 지도에서 지나갈 수 있는 길이 몇 개 있는지 알아보려고 한다. 길이란 한 행 또는 한 열 전부를 나타내며, 한쪽 끝에서 다른쪽 끝까지 지나가는 것이다. 

다음과 같은 N=6인 경우 지도를 살펴보자.

이때, 길은 총 2N개가 있으며, 아래와 같다.

길을 지나갈 수 있으려면 길에 속한 모든 칸의 높이가 모두 같아야 한다. 또는, 경사로를 놓아서 지나갈 수 있는 길을 만들 수 있다. 경사로는 높이가 항상 1이며, 길이는 L이다. 또, 개수는 매우 많아 부족할 일이 없다. 경사로는 낮은 칸과 높은 칸을 연결하며, 아래와 같은 조건을 만족해야한다.

  • 경사로는 낮은 칸에 놓으며, L개의 연속된 칸에 경사로의 바닥이 모두 접해야 한다.
  • 낮은 칸과 높은 칸의 높이 차이는 1이어야 한다.
  • 경사로를 놓을 낮은 칸의 높이는 모두 같아야 하고, L개의 칸이 연속되어 있어야 한다.

아래와 같은 경우에는 경사로를 놓을 수 없다.

  • 경사로를 놓은 곳에 또 경사로를 놓는 경우
  • 낮은 칸과 높은 칸의 높이 차이가 1이 아닌 경우
  • 낮은 지점의 칸의 높이가 모두 같지 않거나, L개가 연속되지 않은 경우
  • 경사로를 놓다가 범위를 벗어나는 경우

L = 2인 경우에 경사로를 놓을 수 있는 경우를 그림으로 나타내면 아래와 같다.

경사로를 놓을 수 없는 경우는 아래와 같다.

위의 그림의 가장 왼쪽부터 1번, 2번, 3번, 4번 예제라고 했을 때, 1번은 높이 차이가 1이 아니라서, 2번은 경사로를 바닥과 접하게 놓지 않아서, 3번은 겹쳐서 놓아서, 4번은 기울이게 놓아서 불가능한 경우이다.

가장 위에 주어진 그림 예의 경우에 지나갈 수 있는 길은 초록색으로, 지나갈 수 없는 길은 빨간색으로 표시되어 있으며, 아래와 같다. 경사로의 길이 L = 2이다.

지도가 주어졌을 때, 지나갈 수 있는 길의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다.

출력

첫째 줄에 지나갈 수 있는 길의 개수를 출력한다.

 

 

 


 

 

접근 방법

 

각각 행에 대해, 열에 대해 연산이 중복되는데 인덱스가 헷갈려서 크기가 2N인 벡터배열에 넣고 동일한 인덱스를 사용했다.

 

 

한칸씩 전진하면서 옆의 요소와 비교하며 길을 탐색하는데, 이때 총 네가지 경우가 있다.

 

1) 옆의 요소와 같을 때 -> sameHeight++ (검사했던 길에 높이가 같은 평평한 길이 얼마나 있는지)

 

2) 옆의 요소의 높이가 1 더 높을 때 -> 이제까지 왔던 길에서 높이가 같아 평평한 길이 L만큼 있는지 체크

 

3) 옆의 요소의 높이가 1 더 낮을 때 -> 앞으로 검사할 길에 높이가 같아 평평한 길이 L만큼 있는지 체크

 

4) 옆의 요소랑 높이 차이가 2 이상일 때 -> stop 하고 다음 검사할 길로 바로 넘어감 

 

 

 

//
//  SM_BOj14890_경사로.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/03/11.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//
//총 경우의 수 4가지 : 같을 때, 1낮을 때, 1높을 때, 높이차 2 이상일 때
//같을 때 : 높이 같은 길의 길이 저장
//1칸 낮을 때 : 앞으로 L만큼 길 연속 됐는지
//1칸 높을 때 : 이전에 L만큼 길 연속 됐었는지
//2 이상일 때 : stop & break

#include <iostream>
#include <vector>
#include <cstring>
#include <cmath>
using namespace std;

int map[100][100];
vector<int> vecArr[200];

int main(){
    
    int ans = 0;
    int N, L;
    cin >> N >> L;
    
    for(int i = 0; i<N; i++){
        for(int j = 0; j<N; j++){
            cin>>map[i][j];
        }
    }
  
    //벡터 배열에 가로 N개, 세로 N개 넣음.
    for(int row=0; row<N; row++){
        for(int col = 0; col<N; col++){
            vecArr[row].push_back(map[row][col]);
        }
    }
    for(int col=0; col<N; col++){
        for(int row=0; row<N; row++){
            vecArr[col+N].push_back(map[row][col]);
        }
    }
    
    
    
    

    for(int i = 0; i<2*N; i++){
        
        bool stop = false;
        int sameHeight = 1;     //기존에 높이 같은 길 얼마나 연속됐는지
        for(int j = 0; j<vecArr[i].size()-1; j++){
            
            if(vecArr[i][j] == vecArr[i][j+1]){ //높이 같은 길 연속되면
                sameHeight++;
                continue;
            }
            
            else if(vecArr[i][j] == vecArr[i][j+1] + 1 ){       //더 낮은 곳을 만났을 때
                
                int cnt = 1;
                bool chk=true;
                for(int k=1; k<L; k++){
                    if(vecArr[i][j+k] == vecArr[i][j+k+1]){	//앞으로 검사할 길에 평평한 길이가 L 만큼 되는지 카운트 
                        cnt++;
                    }
                    else{		//L만큼 다 검사하기도 전에 높이 다른게 있어버리면 
                        chk = false;        //다음 줄로1
                        break;
                    }

                }
                if(chk == false){       //다음 줄로2
                    stop = true;		//그 길은 검사 멈춤
                    break;
                }
                else{
                    if(cnt==L){			//연속된 길 L만큼 있어서 경사로 놓을 수 있으면
                        j += cnt-1;
                        sameHeight = 0;		//1로 초기화하면 예제 4에서 에러 발생 
                    }
                }
            }
            
            
            else if(vecArr[i][j] + 1 == vecArr[i][j+1]){       //더 높은 곳을 만났을 때
                
                if(sameHeight>=L) {	//기존에 평평한 길이가 L보다 긴지 체크 
                    sameHeight = 1;
                    continue;
                }
                else{
                    stop = true;	//경사로 못 놓으면 그 길은 탐색 멈춤
                    break;
                }

            }
            else if (abs(vecArr[i][j] - vecArr[i][j+1]) >= 2){   //높이 차 1 넘을때     -> 이 부분 else 로 하면 틀림
                stop = true;
                break;
                
            }
        }
        
        if(!stop){
            ans++;
           // cout << i << "\n";
        }

    }
    

    cout << ans;
    
    
    return 0;
}

728x90
728x90

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

 

15662번: 톱니바퀴 (2)

총 8개의 톱니를 가지고 있는 톱니바퀴 T개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴

www.acmicpc.net

 

 

문제

총 8개의 톱니를 가지고 있는 톱니바퀴 T개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴가 1번, 그 오른쪽은 2번, ..., 가장 오른쪽 톱니바퀴는 T번이다. 아래 그림은 T가 4인 경우이다.

이때, 톱니바퀴를 총 K번 회전시키려고 한다. 톱니바퀴의 회전은 한 칸을 기준으로 한다. 회전은 시계 방향과 반시계 방향이 있고, 아래 그림과 같이 회전한다.

톱니바퀴를 회전시키려면, 회전시킬 톱니바퀴와 회전시킬 방향을 결정해야 한다. 톱니바퀴가 회전할 때, 서로 맞닿은 극에 따라서 옆에 있는 톱니바퀴를 회전시킬 수도 있고, 회전시키지 않을 수도 있다. 톱니바퀴 A를 회전할 때, 그 옆에 있는 톱니바퀴 B와 서로 맞닿은 톱니의 극이 다르다면, B는 A가 회전한 방향과 반대방향으로 회전하게 된다. 예를 들어, 아래와 같은 경우를 살펴보자.

두 톱니바퀴의 맞닿은 부분은 초록색 점선으로 묶여있는 부분이다. 여기서, 3번 톱니바퀴를 반시계 방향으로 회전했다면, 4번 톱니바퀴는 시계 방향으로 회전하게 된다. 2번 톱니바퀴는 맞닿은 부분이 S극으로 서로 같기 때문에, 회전하지 않게 되고, 1번 톱니바퀴는 2번이 회전하지 않았기 때문에, 회전하지 않게 된다. 따라서, 아래 그림과 같은 모양을 만들게 된다.

위와 같은 상태에서 1번 톱니바퀴를 시계 방향으로 회전시키면, 2번 톱니바퀴가 반시계 방향으로 회전하게 되고, 2번이 회전하기 때문에, 3번도 동시에 시계 방향으로 회전하게 된다. 4번은 3번이 회전하지만, 맞닿은 극이 같기 때문에 회전하지 않는다. 따라서, 아래와 같은 상태가 된다.

톱니바퀴 T개의 초기 상태와 톱니바퀴를 회전시킨 방법이 주어졌을 때, 최종 톱니바퀴의 상태를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 톱니바퀴의 개수 T (1 ≤ T ≤ 1,000)가 주어진다. 

둘째 줄부터 T개의 줄에 톱니바퀴의 상태가 가장 왼쪽 톱니바퀴부터 순서대로 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 시계방향 순서대로 주어진다. N극은 0, S극은 1로 나타나있다.

다음 줄에는 회전 횟수 K(1 ≤ K ≤ 1,000)가 주어진다. 다음 K개 줄에는 회전시킨 방법이 순서대로 주어진다. 각 방법은 두 개의 정수로 이루어져 있고, 첫 번째 정수는 회전시킨 톱니바퀴의 번호, 두 번째 정수는 방향이다. 방향이 1인 경우는 시계 방향이고, -1인 경우는 반시계 방향이다.

출력

총 K번 회전시킨 이후에 12시방향이 S극인 톱니바퀴의 개수를 출력한다.

 

 

 


 

 

 

접근 방법

 

기준 톱니를 중심으로 좌,우를 탐색하면서 N,S극의 상태를 파악해 돌려야하는 톱니의 번호와 회전 방향을 queue에 넣는다.

큐에 넣어 마지막에 한번에 톱니 상태를 갱신해야 한다. 만약 그렇지 않고 오른쪽(또는 왼쪽) 으로 한칸씩 가면서 톱니를 회전시키면 해당 톱니의 N/S극 상태가 바뀌어서 다음 톱니 회전 여부에 영향을 주기 때문에 큐에 넣었다가 한번에 갱신하는 것이다.

 

//기준 톱니를 중심으로 왼쪽, 오른쪽 탐색하면서 돌려야하는 톱니바퀴들 큐에 넣음.
//탐색 끝나고 큐에 있는 톱니들 한번에 갱신(회전) 해야 서로 영향 안줌.
//톱니 하나씩 돌리면 N,S극 계속 바뀌어서 기존 톱니 상태 바뀌어버림

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

vector<int> arrT[1001];
int arrK[1001][2];

void turnRight(int idx){    //idx번째 톱니바퀴 시계방향으로 회전
    
    vector<int> vec = arrT[idx];
    int last = vec[7];
    for(int i=7; i>0; i--){
        vec[i] = vec[i-1];
    }
    vec[0] = last;
    arrT[idx].clear();
    arrT[idx] = vec;
    
}

void turnLeft(int idx){       //idx번째 톱니바퀴 반시계 방향으로 회전
    
    vector<int> vec = arrT[idx];
    int first = vec[0];
    
    for(int i = 0; i<7; i++){
        vec[i] = vec[i+1];
    }
    vec[7] = first;
    
    arrT[idx].clear();
    arrT[idx] = vec;
}

int main(){
    
    int T; cin>>T;
    for(int i = 1; i<=T; i++){
        vector<int> vec;
        for(int j = 0; j<8; j++){
            int n;
            scanf("%1d", &n);
            vec.push_back(n);
        }
        arrT[i] = vec;
    }
    
    int K; cin >> K;
    for(int i = 0; i<K; i++){
        for(int j=0; j<2; j++){
            cin >> arrK[i][j];
        }
        
    }

    queue<pair<int,int>> que;    //회전시켜야하는 톱니바퀴 push
    
    for(int i = 0; i<K; i++){
        
        int center = arrK[i][0];
        int turn = arrK[i][1];

        que.push(make_pair(center,turn));    //기준 톱니바퀴
        
        int right = T - arrK[i][0];     //오른쪽으로 탐색해야하는 톱니바퀴 개수
        int left = T-right-1;           //왼쪽으로 탐색해야하는 톱니바퀴 개수
        
        //1. 오른쪽 탐색
        for(int j = 1; j<=right; j++){
            
            if(arrT[center][2] != arrT[center+1][6]){   //달라서 회전해야할 경우
                turn*=-1;
                que.push(make_pair(center+1, turn));
            }
            else break;
            center++;
        }
        center = arrK[i][0];
        turn = arrK[i][1];
        
        //2. 왼쪽 탐색
        for(int j = 1; j<=left; j++){
            
            if(arrT[center][6] != arrT[center-1][2]){   //달라서 회전해야할 경우
                turn*=-1;
                que.push(make_pair(center-1, turn));
            }
            else break;
            center--;
        }

        while(!que.empty()){
            
            if(que.front().second==1) turnRight(que.front().first);
            else turnLeft(que.front().first);
            
            que.pop();
        }

    }
    

    int ans=0;
    for(int i = 1; i<=T; i++){
        if(arrT[i][0]==1) ans++;
    }
    
    cout << ans;
    
    return 0;
}

728x90
728x90

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

 

16935번: 배열 돌리기 3

크기가 N×M인 배열이 있을 때, 배열에 연산을 R번 적용하려고 한다. 연산은 총 6가지가 있다. 1번 연산은 배열을 상하 반전시키는 연산이다. 1 6 2 9 8 4 → 4 2 9 3 1 8 7 2 6 9 8 2 → 9 2 3 6 1 5 1 8 3 4 2 9 →

www.acmicpc.net

 

 

문제

크기가 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;
}

728x90
728x90

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

 

16927번: 배열 돌리기 2

크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5]

www.acmicpc.net

 

 

문제

크기가 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

 

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

문제 링크 : www.acmicpc.net/problem/16926 16926번: 배열 돌리기 1 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3]..

nanyoungkim.tistory.com

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

 

 

 

예를 들어보자.

  0 1 2 3
0 1 2 3 4
1 5 6 7 8
2 9 10 11 12
3 13 14 15 16

여기서 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;
}

 

728x90
728x90

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

 

16926번: 배열 돌리기 1

크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5]

www.acmicpc.net

 

문제

크기가 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번 반복한다.

 

 

  0 1 2 3
0 1 2 3 4
1 5 6 7 8
2 9 10 11 12
3 13 14 15 16

여기서 박스는

 

  0 1 2 3
0 1 2 3 4
1 5     8
2 9     12
3 13 14 15 16

 

  0 1 2 3
0        
1   6 7  
2   10 11  
3        

이렇게 두개이다.

박스의 시작지점은 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]을 시작지점으로 잡는다.

  0 1 2 3
0 1 2 3 4
1 5 6 7 8
2 9 10 11 12
3 13 14 15 16

 

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

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

 

 

  0 1 2 3
0 1 2 3 4
1 5 6 7 8
2 9 10 11 12
3 13 14 15 16

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

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

 

  0 1 2 3
0 1 2 3 4
1 5 6 7 8
2 9 10 11 12
3 13 14 15 16

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

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

 

  0 1 2 3
0 1 2 3 4
1 5 6 7 8
2 9 10 11 12
3 13 14 15 16

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

 

728x90
728x90

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

 

16931번: 겉넓이 구하기

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

www.acmicpc.net

 

 

문제

크기가 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으로 표시하면 쉽게 계산할 수 있다.

 

  0 1 2 3 4 5
0            
1   o o o o  
2   o o o o  
3   o o o o  
4   o o o o  
5            

 

 

 

#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;
}

 

 

 

 

728x90

+ Recent posts