문제링크: https://www.acmicpc.net/problem/1022
1022번: 소용돌이 예쁘게 출력하기
첫째 줄에 r1, c1, r2, c2가 주어진다. 모두 절댓값이 5000보다 작거나 같은 정수이고, r2-r1은 0보다 크거나 같고, 49보다 작거나 같으며, c2-c1은 0보다 크거나 같고, 4보다 작거나 같다.
www.acmicpc.net
구현문제였습니다. 회오리 모양으로 값이 증가하기에 구현하기 조금 까다로운 문제였습니다.
직관적으로 구현할때 흔히 할 수 있는 실수는
1. 10001 * 10001 의 배열을 만들고 값들을 모두 저장한 후 결과를 도출하는 것입니다.
당연히 메모리 초과입니다..
2. 두번째 저지를 수 있는 실수는 재귀함수로 구현하는 것입니다. 5000번의 재귀가 호출하며 함수 호출과 매개변수 생성 등으로 시간초과를 가지게 됩니다.
우선 정답 코드를 먼저 보여드리겠습니다.
직관적이기 떄문에 쉽게 이해하실 수 있을거라고 생각합니다.
#include <iostream>
#include <algorithm> // max 함수 사용
#include <cmath> // abs 함수 사용
using namespace std;
int r1, c1, r2, c2;
int map[50][5] = { 0 };
void solve() {
int MAX = max(max(abs(r1), abs(c1)), max(abs(r2), abs(c2))); // max값을 찾는다.
int val = 1; //소용돌이에서 값
if (0 >= r1 && 0 >= c1 && 0 <= r2 && 0 <= c2)
map[0 - r1][0 - c1] = val;
int cnt = 0; // 현재의 카운트를 측정
int y = 0, x = 0; // 좌표를 나타냄
for (int i = 1; i <= MAX + 1; i++) {
for (int i = 1; i <= 1 + cnt * 2; i++) {
val++;
x++;
if (y >= r1 && x >= c1 && y <= r2 && x <= c2)
map[y - r1][x - c1] = val;
}
for (int i = 1; i <= 1 + cnt * 2; i++) {
val++;
y--;
if (y >= r1 && x >= c1 && y <= r2 && x <= c2)
map[y - r1][x - c1] = val;
}
for (int i = 1; i <= 2 + cnt * 2; i++) {
val++;
x--;
if (y >= r1 && x >= c1 && y <= r2 && x <= c2)
map[y - r1][x - c1] = val;
}
for (int i = 1; i <= 2 + cnt * 2; i++) {
val++;
y++;
if (y >= r1 && x >= c1 && y <= r2 && x <= c2)
map[y - r1][x - c1] = val;
}
cnt++;
}
}
int main() {
cin >> r1 >> c1 >> r2 >> c2;
solve();
int h = abs(r2 - r1);
int w = abs(c2 - c1);
int MAX = 0;
for (int i = 0; i <= h; i++) {
for (int j = 0; j <= w; j++) {
MAX = max(MAX, map[i][j]);
}
}
//int MAX = max(max(map[0][0], map[0][w - 1]), max(map[h - 1][0], map[h - 1][w - 1]) ); // max값을 찾는다.
int max_degree = 0;
for (int i = 1; i <= MAX; i *= 10) {
max_degree++;
}
for (int i = 0; i <= h; i++) {
for (int j = 0; j <= w; j++) {
int current_degree = 0;
for (int k = 1; k <= map[i][j]; k *= 10)
current_degree++;
for (int k = current_degree; k < max_degree; k++)
cout << ' ';
cout << map[i][j] << ' ';
}
cout << '\n';
}
}solve함수에서 회오리로 이동하는 값들을 계산하면 반복문을 실행하고, 만약 (r1,c1)과 (r2,c2) 값 사이에 있다면 배열에 저장합니다.
그 이후에는 반복문을 통해 최대값의 자릿수를 max_degree에 저장하고 모든 값의 자릿수를 max_degree에 맞춰 적절히 공백을 넣어주면 됩니다.
막상 짜고나면 간단해보이지만 코딩할 때는 어려운게 정석인 문제...
좀 더 효율적인 방법이 많을거 같아서 코드를 찾아봤습니다.
#include<cstdio>
int a[50][50], r1, c1, r2, c2, m, s;
int main() {
scanf("%d%d%d%d", &r1, &c1, &r2, &c2);
for (int i = r1; i <= r2; i++) {
for (int j = c1; j <= c2; j++) {
int x = i - r1, y = j - c1;
if (i - j < 0) {
if (i + j < 0) a[x][y] = 4 * i*i + i + 1 - j;
else a[x][y] = 4 * j*j - 3 * j + 1 - i;
}
else {
if (i + j < 0) a[x][y] = 4 * j*j - j + 1 + i;
else a[x][y] = 4 * i*i + 3 * i + 1 + j;
}
if (a[x][y] > m) m = a[x][y];
}
}
for (; m; m /= 10) s++;
for (int i = 0; i <= r2 - r1; i++) {
for (int j = 0; j <= c2 - c1; j++) printf("%*d ", s, a[i][j]);
puts("");
}
return 0;
}
너무 간결하게 예쁜코드네요.
애초에 회오리가 규칙있게 값이 증가하기에 경우마다 값을 계산해서 O(200)만에 해결한 방법입니다.
저렇게 짤 수 있으면 정말 잘하시는거겠지만 좋은 코드의 조건을 여러가지가 있을 수 있습니다.
어떤 사람에게는 직관적이고 이해하기 쉬운 코드일수도, 다른 사람에게는 짧고 시간이 짧게 드는 것일 수도 있습니다.
사람마다 기준이 다르기에 어떤게 옳다고 볼 수는 없습니다.
꼭 직접 보지않고 구현해보세요. 구현문제의 핵심은 연습입니다.
화이팅 :)
'알고리즘 > 구현' 카테고리의 다른 글
| [백준] 1756-피자 굽기(C++) (0) | 2020.05.08 |
|---|---|
| [백준] 1188-음식 평론가(C++) (0) | 2020.05.03 |
| [백준] 5567-결혼식(C++) (0) | 2020.04.27 |
| [백준] 2851-슈퍼 마리오(C++) (0) | 2020.04.26 |
| [백준] 8979-올림픽(C++) (0) | 2020.04.26 |
