728x90

0. 주어진 문제 

소용돌이 예쁘게 출력하기 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초128 MB3985107783631.559%

문제

크기가 무한인 정사각형 모눈종이가 있다. 모눈종이의 각 정사각형은 행과 열의 쌍으로 표현할 수 있다.

이 모눈종이 전체를 양의 정수의 소용돌이 모양으로 채울 것이다. 일단 숫자 1을 0행 0열에 쓴다. 그리고 나서 0행 1열에 숫자 2를 쓴다. 거기서 부터 소용돌이는 반시계 방향으로 시작된다. 다음 숫자는 다음과 같이 채우면 된다.

    -3 -2 -1  0  1  2  3
    --------------------
-3 |37 36 35 34 33 32 31
-2 |38 17 16 15 14 13 30
-1 |39 18  5  4  3 12 29
 0 |40 19  6  1  2 11 28
 1 |41 20  7  8  9 10 27
 2 |42 21 22 23 24 25 26
 3 |43 44 45 46 47 48 49

이 문제는 위와 같이 채운 것을 예쁘게 출력하면 된다. r1, c1, r2, c2가 입력으로 주어진다. r1, c1은 가장 왼쪽 위 칸이고, r2, c2는 가장 오른쪽 아래 칸이다.

예쁘게 출력한다는 것은 다음과 같이 출력하는 것이다.

  1. 출력은 r1행부터 r2행까지 차례대로 출력한다.
  2. 각 원소는 공백으로 구분한다.
  3. 모든 행은 같은 길이를 가져야 한다.
  4. 공백의 길이는 최소로 해야 한다.
  5. 모든 숫자의 길이(앞에 붙는 공백을 포함)는 같아야 한다.
  6. 만약 수의 길이가 가장 길이가 긴 수보다 작다면, 왼쪽에서부터 공백을 삽입해 길이를 맞춘다.

입력

첫째 줄에 r1, c1, r2, c2가 주어진다. 모두 절댓값이 5000보다 작거나 같은 정수이고, r2-r1은 0보다 크거나 같고, 49보다 작거나 같으며, c2-c1은 0보다 크거나 같고, 4보다 작거나 같다.

출력

r2-r1+1개의 줄에 소용돌이를 예쁘게 출력한다.

예제 입력 1 

-3 -3 2 0

예제 출력 1 

37 36 35 34
38 17 16 15
39 18  5  4
40 19  6  1
41 20  7  8
42 21 22 23



 1. 풀이


처음 생각했을 때, 돌아가는 소용돌이를 모두 구현하는 것을 생각해보았다.

모두 구현한 뒤, 내가 원하는 구간만 출력하는 형태로 구현을 했었는데 입력이 커지니 메모리 제한을 초과하는 일이 발생하였다.


따라서, 배열의 크기는 arr[5][50]으로 고정하고 조건에 맞는 수만 배열에 넣는 형태로 구현을 하였다.


사실 배열은 5*50이고, 숫자의 규칙성이 있으니 구현을 조금만 잘하면의 수준으로 구현을 해낼 수도 있을 것 같았지만, 나의 구현은 의 구현으로 되어있다.

허나, 문제의 입력이 5000까지이므로, 충분히 시간 내에 해결이 가능하였기에 따로 수정을 하지는 않았다.


 2. 소스코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<iostream>
#include<algorithm>    //max()를 사용하기 위한 헤더
#include<string>    //to_string()을 사용하기 위한 헤더
#include<cstdlib>    //abs()를 사용하기 위한 헤더
 
using namespace std;
 
int Count;
int arr[5][50];
int max_length;
 
void make_vortex(int y1, int x1, int y2, int x2){
    //절댓값 중 최대값을 구한다.
    int MAX = max(max(abs(y1),abs(x1)),max(abs(y2),abs(x2)));
    //pos_x, pos_y는 현재 위치이다.
    int pos_x, pos_y;
    pos_x = pos_y = 0;
    //count는 지금 출력해야 할 값이다.
    ++Count;
 
    //현재 위치가 찾아야 할 위치 사이라면 출력한다.
    if ((x1 <= pos_x && pos_x <= x2) && (y1 <= pos_y && pos_y <= y2))
        arr[pos_x - x1][pos_y - y1] = Count;
 
 
    for (int i = 1; i <= MAX; i++) {
        //pos_x, pos_y는 현재 위치를 나타내는 것으로, 계속적으로 증가, 감소를 해준다.
        ++pos_x;
        ++pos_y;
        int flag = 0;
        for (int j = 1; j <= i * 8; j++) {
            switch (flag)
            {
            case 0:
                --pos_y;
                ++Count;
                //현재 위치가 찾아야 할 위치 사이라면 출력한다.
                if ((x1 <= pos_x && pos_x <= x2) && (y1 <= pos_y && pos_y <= y2))
                    arr[pos_x - x1][pos_y - y1] = Count;
                break;
 
            case 1:
                --pos_x;
                ++Count;
                if ((x1 <= pos_x && pos_x <= x2) && (y1 <= pos_y && pos_y <= y2))
                    arr[pos_x - x1][pos_y - y1] = Count;
                break;
 
            case 2:
                ++pos_y;
                ++Count;
                if ((x1 <= pos_x && pos_x <= x2) && (y1 <= pos_y && pos_y <= y2))
                    arr[pos_x - x1][pos_y - y1] = Count;
                break;
 
            case 3:
                ++pos_x;
                ++Count;
                if ((x1 <= pos_x && pos_x <= x2) && (y1 <= pos_y && pos_y <= y2))
                    arr[pos_x - x1][pos_y - y1] = Count;
                break;
            }
            if (j%(i * 2) == 0) flag++;
        }
    }
}
 
int main() {
    int x1, y1, x2, y2;
    cin >> y1 >> x1 >> y2 >> x2;
    make_vortex(y1,x1,y2,x2);
    int temp, sub;
    for (int y = 0; y < (y2 - y1) + 1; y++) {
        for (int x = 0; x < (x2 - x1) + 1; x++) {
            //배열의 수에서 가장 긴 수의 자리수를 찾는다.
            temp = to_string(arr[x][y]).length();
            max_length = max(temp, max_length);
        }
    }
    
    for (int y = 0; y < (y2-y1)+1; y++) {
        for (int x = 0; x < (x2-x1)+1; x++) {
            //지금 출력할 수의 길이가 최대 길이보다 짧다면 그 차이만큼 " "(공백)을 출력한다.
            sub = max_length - to_string(arr[x][y]).size();
            for (int i = 0; i < sub; i++) {
                cout << " ";
            }
            //숫자를 출력.
            cout << arr[x][y] << " ";
        }
        cout << endl;
    }
}
cs


 3. 문제 출처


https://www.acmicpc.net/problem/1022


 4. 참고


구종만, 「프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략」, 인사이트, 2012, p.216~236.


저작자표시

'<백준> > |C++| hard' 카테고리의 다른 글

[C++] 백준 1107 - 리모컨(brute force)  (4) 2019.04.24
[c++] 백준 2981 - 검문  (0) 2019.04.17
[C++] 백준 11066 - 파일 합치기(동적 계획법, 이후에 다시 보자)  (0) 2019.04.16
[C++] 백준 1005 - ACM Craft(동적 계획법, 메모이제이션)  (0) 2019.04.10
[c++] 백준 11401 - 이항 계수 3(페르마의 소정리, 확장 유클리드 호제법, 베주 방정식)  (0) 2019.04.04

+ Recent posts

티스토리툴바