[백준]][C++] 1022 소용돌이 예쁘게 출력하기

www.acmicpc.net/problem/1022

1022번: 소용돌이 예쁘게 출력하기

 

 

 

알고리즘 종류

    - 구현

 

 

 

사고 과정

    - 소용돌이 만들기

        1. 소용돌이는 중심에서 시작해서 2번씩 같은 거리를 이동한다.

        2. 소용돌이는 원하는 배열이 다 차면 멈춘다.

 

    - 출력

        1. 배열 내에서 최대 길이 숫자에 맞춰서 출력해야 한다.

        2. 최대 길이 숫자를 찾고, 길이에 맞춰서 출력한다.

 

 

 

구현(C++)

#include <iostream>
#include <vector>
#include <cmath>
#include <cstring>
 
using namespace std;
 
 
int r1, r2, c1, c2;
int mat[50][5];
int dir[4][2] = {{0,1}, {-1,0}, {0,-1}, {1,0}}; 
 
 
 
void print(){
    
    int r = r2 - r1;
    int c = c2 - c1;
    
    // 알맞게 출력하기 위해서 최고 큰 숫자의 자릿수 구하기
    int num = max(mat[0][0], mat[r][c]);
    int cnt=0;
    while(num){
        num /= 10;
        cnt++;
    }
    
    // 최고 큰 자릿수에 맞춰서 출력하기
    for (int i=0; i<=r; i++) {
        for (int j=0; j<=c; j++) {
            printf("%*d ", cnt, mat[i][j]);
        }
        printf("\n");
    }
}
 
// 소용돌이 
void whirl(){
    
    int r = r2 - r1;
    int c = c2 - c1;
    
    int y = 0;
    int x = 0;
 
    int move = 1;
    int cnt = 1;
    int d = 0;
    
    while(true){
        // 2회
        for(int i=0; i<2; i++){
            // 이동 거리 만큼 이동
            for(int j=0; j<move; j++){
                // 원하는 범위일 때만 저장하기
                if((y >= r1 && y <= r2) && (x >= c1 && x <= c2))
                    mat[y-r1][x-c1] = cnt;
                    
                y += dir[d][0];
                x += dir[d][1];
                cnt++;
            }
            
            if(d==0) d=1;
            else if(d==1) d=2;
            else if(d==2) d=3;
            else if(d==3) d=0;
            
        }
        move++;
        // 원하는 범위가 다 찼으면 종료
        if((mat[0][0] && mat[r][0]) && (mat[r][c] && mat[0][c])) break;
    }
}
 
 
 
int main(void){
    
    //memset(mat, 0, sizeof(mat));
    scanf("%d %d %d %d", &r1, &c1, &r2, &c2);
    
    whirl();
    print();
}

 

 

 

시행착오

    - 배열 mat에 소용돌이 전체를 저장하고 부분만 출력하려고 하니 메모리 초과가 났었다. 10^8 * 4 bytes니 400mb였다. 생각해보니 모두 배열에 저장하지 않아도 됬다. 소용돌이를 만들면서, y와 x값이 범위에 들어간다면, 그 값만 저장하면 됬다.