1022번 - 소용돌이 예쁘게 출력하기
1. 문제
크기가 무한인 정사각형 모눈종이가 있다. 모눈종이의 각 정사각형은 행과 열의 쌍으로 표현할 수 있다.
이 모눈종이 전체를 양의 정수의 소용돌이 모양으로 채울 것이다. 일단 숫자 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
이 문제는 위와 같이 채운 것을 예쁘게 출력하면 된다. $r_1$, $c_1$, $r_2$, $c_2$ 가 입력으로 주어진다. $r_1$, $c_1$ 은 가장 왼쪽 위 칸이고, $r_2$, $c_2$ 는 가장 오른쪽 아래 칸이다.
예쁘게 출력한다는 것은 다음과 같이 출력하는 것이다.
- Input
첫째 줄에 네 정수 $r_1$, $c_1$, $r_2$, $c_2$ 가 주어진다.
- Output
$r_2 - r_1 + 1$ 개의 줄에 소용돌이를 예쁘게 출력한다.
- $-5 \ 000 \le r_1, \ c_1, \ r_2, \ c_2 \le 5 \ 000$
- $0 ≤ r_2 - r_1 ≤ 49$
- $0 ≤ c_2 - c_1 ≤ 4$
2. 사용 알고리즘
2.1. 알고리즘
- 수학
- 구현
3. 풀이
해당 풀이는 가능한 한 코드의 길이를 줄이고자 하는 숏코딩 방식으로 구현되었다.
이 문제의 풀이를 구상할 때, 가장 먼저 2차원 배열을 설정한 후 해당 배열에 소용돌이 형태의 반복문을 구성하여 숫자를 할당하는 방식을 생각하였다. 하지만 해당 풀이는 배열이 최대 $5000 \times 5000$ 의 공간을 필요로 한다. 이는 메모리 초과가 우려되어 폐기하였다.
더 나아가 필요한 만큼만 축소된 배열을 사용하여 구현하였지만 최대 $5000 \times 5000$ 번의 반복을 피할 수 없어
-5000 -5000 -4999 -4999와 같은 입력의 경우 출력까지 너무 오랜시간이 걸렸다. 이 역시 시간 초과가 우려되어 폐기하였다.
다른 구현 방식을 생각하다가 일정한 규칙에 따른 수열이 존재한다고 판단하여 일반화된 계산식을 구하여 문제를 해결하였다.
3.1. 2차원 수열
해당 문제는 임의의 정수 $r$, $c$ 에 대하여 다음의 2차원 수열의 일반식 $a_{r, c}$ 를 구한다면 해결할 수 있다.
$$
\forall r \in [ r_1, r_2 ], \ \forall c \in [ c_1, c_2 ], \ a_{r, c} = N
$$
3.2. 소용돌이 수열
위 이미지는 숫자 $1$ 을 정중앙으로 하여 $9 \times 9$ 테이블에 $81$ 까지의 소용돌이 수열을 나타낸 것이다.
3.3. 범위 구분
해당 수열을 $r$, $c$ 만으로 해당 위치에 존재하는 숫자 $N$ 을 구하기 위해서는 반드시 범위 구분이 필요하다.
[이미지 1] 의 소용돌이 수열에서 방향이 꺾이는 곳의 숫자를 표시하면 다음과 같다.
위에서 나타낸 경계선을 기준으로 다음과 같은 네 개의 구역으로 나누어 계산한다.
편의 상 주황색 구역을 $A$, 파란색 구역을 $B$, 빨간색 구역을 $C$, 초록색 구역을 $D$ 로 지칭한다.
구역 $A$, $B$, $C$, $D$ 를 나누는 기준은 다음과 같다.
| $A$ | $B$ | $C$ | $D$ |
|---|---|---|---|
| $| r | \ge | c |$ | $| r | \ge | c |$ | $| r | \lt | c |$ | $| r | \lt | c |$ |
| $r \ge 0$ | $r \lt 0$ | $c \gt 0$ | $r \lt 0$ |
각 구역의 숫자들은 피라미드 형태로 존재한다. 변수는 $r$, $c$ 로 총 2개 존재하는데, 피라미드 각 층의 첫 번째 숫자를 알고 있다면 $c$ 의 정보만을 가지고 해당 층 나머지 숫자들에 대해 충분히 유추할 수 있다.
따라서 일차적으로 각 층의 첫 번째 숫자로 이루어진 수열의 일반식을 구한 후, 나머지 숫자들은 변수 $r$ 와 $c$ 의 값을 적절히 혼합하여 일반식을 구하는 과정으로 진행하고자 한다.
3.3.1. $A$ 구역
$A$ 구역은 $| r | \ge | c |$, $r \ge 0$ 을 만족하는 구역이다.
위 이미지를 통해 $A$ 구역 각 층의 첫 번째 숫자로 이루어진 수열은 ${ a_{r, -r} }$ 으로 행과 열이 서로 절댓값이 같고 부호가 반대인 경우임을 확인할 수 있다.
| $r$ | $0$ | $1$ | $2$ | $3$ | $4$ | $\cdots$ |
|---|---|---|---|---|---|---|
| $a_{r, -r}$ | $1$ | $7$ | $21$ | $43$ | $73$ | $\cdots$ |
위 수열 $a_{r, -r}$ 의 일반식은 다음과 같다.
$$
a_{r, -r} = 1 + 2 \sum _{i = 0} ^{2r} {i} = 1 + 2 r \left( 2r + 1 \right)
$$
위 식을 $A$ 구역의 모든 숫자에 대하여 확장하면 다음과 같다.
$$
a_{r, c} = 1 + 2 r \left( 2r + 1 \right) + \left( r + c \right)
$$
3.3.2. $B$ 구역
$B$ 구역은 $| r | \ge | c |$, $r \lt 0$ 을 만족하는 구역이다.
$B$ 구역 역시 $A$ 구역과 마찬가지로 각 층의 첫 번째 숫자로 이루어진 수열이 ${ a_{r, -r} }$ 이다.
| $r$ | $-1$ | $-2$ | $-3$ | $-4$ | $\cdots$ |
|---|---|---|---|---|---|
| $a_{r, -r}$ | $3$ | $13$ | $31$ | $57$ | $\cdots$ |
일반식은 다음과 같다.
$$
a_{r, -r} = 1 + 2 \sum _{i = -1} ^{-2r - 1} {i} = 1 + \left( -2r - 1 \right) \left( -2r \right) = 1 + 2r \left( 2r + 1 \right)
$$
위 식을 $B$ 구역의 모든 숫자에 대하여 확장하면 다음과 같다.
$$
a_{r, c} = 1 + 2 r \left( 2r + 1 \right) - \left( r + c \right)
$$
3.3.3. $C$ 구역
$C$ 구역은 $| r | \lt | c |$, $c \gt 0$ 을 만족하는 구역이다.
$C$ 구역은 각 층의 첫 번째 숫자로 이루어진 수열이 ${ a_{c - 1, c} }$ 이다.
| $c$ | $1$ | $2$ | $3$ | $4$ | $\cdots$ |
|---|---|---|---|---|---|
| $a_{c - 1, c}$ | $2$ | $10$ | $26$ | $50$ | $\cdots$ |
일반식은 다음과 같다.
$$
a_{c - 1, c} = 2 \sum _{i = 1} ^{2c - 1} {i} - 2 \left(c - 1 \right) = 2c \left( 2c - 1 \right) + 2 - 2c
$$
위 식을 $C$ 구역의 모든 숫자에 대하여 확장하면 다음과 같다.
$$
a_{r, c} = 2c \left( 2c - 1 \right) + 2 - 2c + (c - r) - 1 \\ = 1 + 2c \left( 2c - 1 \right) - \left( r + c \right)
$$
3.3.4. $D$ 구역
$D$ 구역은 $| r | \lt | c |$, $c \lt 0$ 을 만족하는 구역이다.
$D$ 구역은 각 층의 첫 번째 숫자로 이루어진 수열이 ${ a_{c + 1, c} }$ 이다.
| $c$ | $-1$ | $-2$ | $-3$ | $-4$ | $\cdots$ |
|---|---|---|---|---|---|
| $a_{c + 1, c}$ | $6$ | $18$ | $38$ | $66$ | $\cdots$ |
일반식은 다음과 같다.
$$
a_{c + 1, c} = 2 \sum _{i = -1} ^{2c} {i} + 2 \left(c + 1 \right) = - 2c \left( -2c + 1 \right) + 2 + 2c \\
= 2c \left( 2c - 1 \right) + 2 + 2c
$$
위 식을 $D$ 구역의 모든 숫자에 대하여 확장하면 다음과 같다.
$$
a_{r, c} = 2c \left( 2c - 1 \right) + 2 + 2c - \left( c - r \right) - 1 \\
= 1 + 2c \left( 2c - 1 \right) + \left( r + c \right)
$$
3.4. 전체 일반식 정리
모든 구역의 일반식을 나타내면 다음과 같다.
$$
a_{r,c} =
\begin{cases}
1 + 2 r \left( 2r + 1 \right) + \left( r + c \right) & \text{if} \ \left( | r | \ge | c | \right) \land \left( r \ge 0 \right) \\ 1 + 2 r \left( 2r + 1 \right) - \left( r + c \right) & \text{if} \ \left( | r | \ge | c | \right) \land \left( r \lt 0 \right) \\ 1 + 2c \left( 2c - 1 \right) - \left( r + c \right) & \text{if} \ \left( | r | \lt | c | \right) \land \left( c \gt 0 \right) \\ 1 + 2c \left( 2c - 1 \right) + \left( r + c \right) & \text{if} \ \left( | r | \lt | c | \right) \land \left( c \lt 0 \right)
\end{cases}
$$
네 가지 경우로 나누어 생각했지만 서로 상당히 유사한 형태가 나온다는 것을 확인할 수 있다.
3.5. 일반식 단순화
일반식의 조건부를 삭제하고 모든 $r$, $c$ 에 대해 하나의 식으로써 원하는 숫자 $N$ 을 구하고자 한다.
먼저 다음의 두 변수를 정의하자.
$$
m = \max( |r|, |c| ) \\ d = \text{sign} \left( r - c \right)
$$
위 변수를 활용하여 일반식 $a_{r,c}$ 를 다음과 같이 나타낼 수 있다.
$$
a_{r,c} =
\begin{cases}
1 + 2m \left( 2m + 1 \right) + \left( r + c \right) & \text{if} \ \left( | r | \ge | c | \right) \land \left( r \ge 0 \right) \\ 1 + 2m \left( 2m - 1 \right) - \left( r + c \right) & \text{if} \ \left( | r | \ge | c | \right) \land \left( r \lt 0 \right) \\ 1 + 2m \left( 2m - 1 \right) - \left( r + c \right) & \text{if} \ \left( | r | \lt | c | \right) \land \left( c \gt 0 \right) \\ 1 + 2m \left( 2m + 1 \right) + \left( r + c \right) & \text{if} \ \left( | r | \lt | c | \right) \land \left( c \lt 0 \right)
\end{cases}
$$
정리하면
$$
a_{r,c} =
\begin{cases}
1 + 4m^2 + (2m + r + c) & \text{if} \ \left( | r | \ge | c | \right) \land \left( r \ge 0 \right) \\ 1 + 4m^2 - (2m + r + c) & \text{if} \ \left( | r | \ge | c | \right) \land \left( r \lt 0 \right) \\ 1 + 4m^2 - (2m + r + c) & \text{if} \ \left( | r | \lt | c | \right) \land \left( c \gt 0 \right) \\ 1 + 4m^2 + (2m + r + c) & \text{if} \ \left( | r | \lt | c | \right) \land \left( c \lt 0 \right)
\end{cases}
$$
이므로 최종적으로 아래와 같은 식으로 나타낼 수 있다.
$$
a_{r,c} = 1 + 4 m ^2 + d \left( 2m + r + c \right)
$$
4. 구현
이제 실제로 구현해보자.
4.1. 값 입력
한 줄에 네 정수를 입력받기위해 다음과 같이 구현한다.
r1, c1, r2, c2 = map(int, input().split())4.2. sign() 함수
매개변수의 부호를 반환하는 sign() 함수는 다음과 같이 나타낼 수 있다.
$$
\text{sign} (x) =
\begin{cases}
1 & \text{if} \ \ x \ge 0 \\ -1 & \text{if} \ \ x \lt 0
\end{cases}
$$
이는 코드로 다음과 같이 구현하였다.
sign = lambda x: 1 - 2 * (x < 0)4.3. get_number() 함수
매개변수 r, c 를 받아 해당 위치에 있는 숫자를 반환하는 함수이다. 위에서 언급한 $a_{r,c}$ 의 일반식과 일맥상통한다.
$$
m = \max( |r|, |c| ) \\ d = \text{sign} \left( r - c \right)
$$
$$
a_{r,c} = 1 + 4 m ^2 + d \left( 2m + r + c \right)
$$
def get_number(r, c):
m, d = max(abs(r), abs(c)), sign(r - c)
return 1 + 4 * m * m + d * (2 * m + r + c)4.4. 출력
다음과 같이 이중 for 문을 사용하여 2차원 수열을 출력하면 된다.
for i in range(r1, r2 + 1):
print(' '.join(get_number(i, j) for j in range(c1, c2 + 1)))4.5. 공백 삽입 Formatting
다만 이는 문제에 주어진 6번째 조건을 고려하지 않은 풀이다.
- 만약 수의 길이가 가장 길이가 긴 수보다 작다면, 왼쪽에서부터 공백을 삽입해 길이를 맞춘다.
우리는 출력할 때 출력될 모든 숫자의 길이 최댓값을 미리 알고 있어야 한다. 이 말은 즉, 반복문을 2회 반복하여 첫 반복 때 미리 최댓값을 저장한 후 마지막 반복 때 해당 값을 적용한 format 으로 출력하여야 함을 의미한다.
numlen = 0
for i in range(r1, r2 + 1):
for j in range(c1, c2 + 1):
numlen = max(numlen, len(str(get_number(i, j))))
fmt = f'%{numlen}d'
for i in range(r1, r2 + 1):
print(' '.join(fmt % get_number(i, j) for j in range(c1, c2 + 1)))하지만 이는 효율적이지 못하게 여겨졌고, 다른 대안이 있는지 모색하게 되었다.
4.5.1. 다른 방법은 없는가?
다른 방법이 바로 직사각형의 꼭짓점 (좌상단 $a_{r_1, c_1}$, 우상단 $a_{r_1, c_2}$, 좌하단 $a_{r_2, c_1}$, 우하단 $a_{r_2, c_2}$) 숫자 4개를 확인하는 방법이다.
해당 2차원 수열에 어느부분에 직사각형을 위치시켜도 직사각형 내 존재하는 수 중 가장 큰 수는 반드시 이 네 숫자 안에 존재한다. 그 이유는 다음과 같다.
- $R_n$: 직사각형 $r_n$ 행에 존재하는 숫자의 집합
- $C_n$: 직사각형 $c_n$ 열에 존재하는 숫자의 집합
- $O = R_1 \cup R_2 \cup C_1 \cup C_2$
- 수열은 밖을 향하여 점점 커진다.
- 최댓값은 $O$ 에 존재한다.
- $R_1 \cup C_1$ 또는 $C_1 \cup R_2$ 또는 $R_2 \cup C_2$ 또는 $C_2 \cup R_1$ 은 공차가 $1$ 인 등차수열을 포함한다.
- 이때 반드시 해당 등차수열의 말단 숫자 (최댓값)는 직사각형 꼭짓점에 존재하게 된다.
따라서 다음의 코드로 구현될 수 있다.
numlen = len(str(max(
get_number(r1, c1),
get_number(r1, c2),
get_number(r2, c1),
get_number(r2, c2),
)))
fmt = f'%{numlen}d'
for i in range(r1, r2 + 1):
print(' '.join(fmt % get_number(i, j) for j in range(c1, c2 + 1)))4.5.2. 이게 최선인가?
그렇다면 매번 꼭짓점 4개 숫자를 모두 확인해야 할까? 그전에 일단 어떤 지점을 조사해야 하는지 알아볼 필요가 있다.
출력될 모든 숫자의 길이 최댓값을 구하기 위해서 직사각형 내 숫자의 길이가 바뀌는 즉, 자릿수가 1 증가하는 지점이 있는지와 위치는 어디인지 파악할 필요가 있다. 해당 지점이 직사각형의 꼭짓점에 위치할 때가 관건이 되는데, 반드시 해당 꼭짓점을 조사하여야 하기 때문이다.
즉, 우리는 $10^n \ (n = 1, 2, 3, \cdots)$ 의 위치를 파악할 필요가 있다.
위에서 언급한 상황은 다음의 8가지 경우로 나타낼 수 있다.
- 특정 두 개의 꼭짓점 중 하나를 조사해야 하는 경우
- 특정 한 개의 꼭짓점을 반드시 조사해야 하는 경우
길이가 1 커지는 지점이 정확히 방향 꺾이는 지점에 존재하는 경우이다.
A 경우를 제외한 모든 경우이다.
다음은 위 이미지에 대한 설명이다.
- 화살표의 방향은 숫자가 커지는 방향이다.
- 대각화살표는 숫자가 커지는 방향이 꺾이는 지점이다.
- 파란색 지점 숫자 길이가 주황색 지점의 숫자 길이보다 1 크다.
- 검은색 직사각형은 사용자 입력값에 해당하는 직사각형이다.
- 진한 파란색 지점은 직사각형 꼭짓점 숫자 중 최대 길이를 갖는 지점이다.
문제에는 다음의 제약사항이 명시되어 있다.
- $-5 \ 000 \le r_1, \ c_1, \ r_2, \ c_2 \le 5 \ 000$
이는 파악해야 할 $10^n$ 의 위치의 개수가 유한함을 의미한다. 2차원 수열에는 $100 \ 000 \ 000 = 10^8$ 까지 존재할 수 있으므로 $n = 1, 2, \cdots , 8$ 의 8가지 경우를 모두 파악하면 된다.
- $n = 2k (k = 1, 2, 3, \cdots)$ 일 때
$n$ 이 짝수라면 모든 경우 다 B-1 에 해당한다. $1$ 부터 시작하여 북서쪽으로 증가하는 수열 $NE$ 은 반드시 짝수 제곱수에 $1$ 을 더한 일반식을 갖기 때문이다.
$$
{ NE_n } = { 1, 5, 17, 37, 65, \cdots } \\ NE_n = (2n)^2 + 1
$$$10^{2k} = (10^k)^2$ 이므로 $10^{2k}$ 는 $10^k$ 의 제곱수이고, 해당 숫자는 반드시 좌상단 꼭짓점(남서향대각화살표 ↙ 지점)의 1칸 오른쪽에 위치하게 된다.
따라서 좌상단 꼭짓점 $a_{r_1, c_1}$ 은 반드시 조사하여야 한다. - $n = 2k - 1 (k = 1, 2, 3, \cdots)$ 일 때
$n$ 이 홀수라면 $10^n$ 이 제곱수가 될 수 없기 때문에 어떠한 경우에 해당하는지 알 수 없어 모든 경우를 조사해야 한다.
- $n = 1$
$a_{1, 2} = 10^1 = 10$ 이고, $10$ 은 A-4 에 해당한다.
[이미지 20] 소용돌이 수열에서 숫자 $10$ 의 위치
이에 따라 우상단 꼭짓점 $a_{r_1, c_2}$ 또는 우하단 꼭짓점 $a_{r_2, c_2}$ 를 조사하여야 한다. - $n = 3$
$a_{-16, 9} = 10^3 = 1 \ 000$ 이고, $1 \ 000$ 은 B-1 에 해당한다.
[이미지 21] 소용돌이 수열에서 숫자 $1 \ 000$ 의 위치
따라서 좌상단 꼭짓점 $a_{r_1, c_1}$ 은 반드시 조사하여야 한다. - $n = 5$
$a_{-15, -159} = 10^5 = 100 \ 000$ 이고, $100 \ 000$ 은 B-3 에 해당한다.
[이미지 22] 소용돌이 수열에서 숫자 $100 \ 000$ 의 위치
따라서 좌하단 꼭짓점 $a_{r_2, c_1}$ 은 반드시 조사하여야 한다. - $n = 7$
$a_{174, -1581} = 10^7 = 10 \ 000 \ 000$ 이고, $10 \ 000 \ 000$ 은 B-3 에 해당한다.
[이미지 23] 소용돌이 수열에서 숫자 $10 \ 000 \ 000$ 의 위치
따라서 좌하단 꼭짓점 $a_{r_2, c_1}$ 은 반드시 조사하여야 한다.
- $n = 1$
정리하면 좌상단 꼭짓점 $a_{r_1, c_1}$ 과 좌하단 꼭짓점 $a_{r_2, c_1}$ 은 반드시 조사하여야 하고, 우상단 꼭짓점 $a_{r_1, c_2}$ 과 우하단 꼭짓점 $a_{r_2, c_2}$ 중 하나를 조사하여야 한다.
이말은 즉, 조사 꼭짓점 수를 하나 줄일 수 있다는 의미가 되며, 해당 증명은 숏코딩에서 진가를 발휘하게 된다.
코드는 다음과 같다.
numlen = len(str(max(
get_number(r1, c1),
get_number(r2, c1),
get_number(r2, c2),
)))4.6. 숏코딩
아래의 작업을 수행하면 최종적으로 숏코딩이 완성된다.
- 공백제거
- 변수이름 단순화
- 일회성 변수 및 함수 제거
- 등등 줄일 수 있는 것 최대한 ...
5. 제출 코드
1차
맞았습니다!!
r1, c1, r2, c2 = map(int, input().split())
rows = r2 - r1 + 1
cols = c2 - c1 + 1
def get_number(r, c):
sr, sc = map(lambda x: 2 * (x >= 0) - 1, [r, c])
if abs(r) >= abs(c): return 1 + 2 * r * (2 * r + 1) + (r + c) * sr
return 2 * c * (2 * c - 1) + 2 - 2 * c * sc + (c - r) * sc - 1
numlen = len(str(max(
get_number(r1, c1), get_number(r1, c2),
get_number(r2, c1), get_number(r2, c2),
)))
fmt = '{:' + str(numlen) + 'd}'
for i in range(rows):
for j in range(cols):
if j: print(end=' ')
number = get_number(i + r1, j + c1)
print(fmt.format(number), end='')
print()다음은 조금 급하게 짠 코드의 티가 나는 부분이다.
return 2 * c * (2 * c - 1) + 2 - 2 * c * sc + (c - r) * sc - 1깔끔하지 않은 식으로 제출하여 마음에 들지 않았다.
2차
맞았습니다!!
r1, c1, r2, c2 = map(int, input().split())
rows = r2 - r1 + 1
cols = c2 - c1 + 1
sign = lambda x: 1 - 2 * (x < 0)
def get_number(r, c):
m, d = max(abs(r), abs(c)), sign(r - c)
return 1 + 4 * m * m + d * (2 * m + r + c)
numlen = len(str(max(
get_number(r1, c1),
get_number(r2, c1),
get_number(r2, c2),
)))
fmt = f'%{numlen}d'
for i in range(r1, r2 + 1):
print(' '.join(fmt % get_number(i, j) for j in range(c1, c2 + 1)))출력부를
for i in range(rows):
print(' '.join(fmt % get_number(i + r1, j + c1) for j in range(cols)))에서
for i in range(r1, r2 + 1):
print(' '.join(fmt % get_number(i, j) for j in range(c1, c2 + 1)))로 변경하게 됨으로써 사용하지 않는
rows = r2 - r1 + 1
cols = c2 - c1 + 1의 변수 선언부를 삭제하지 않고 제출하였다.
3차 Short
맞았습니다!!
w,x,y,z=map(int,input().split());s=lambda n:1-2*(n<0)
def g(i,j):m,d=max(abs(i),abs(j)),s(i-j);return(2*m+i+j)*d+1+4*m*m
l=len(str(max(g(w,x),g(y,x),g(y,z))))
print('\n'.join(' '.join(f'%{l}d'%g(i,j)for j in range(x,z+1))for i in range(w,y+1)))본격적인 첫 제출 숏코드인데 제출 전 수없이 확인해 보았음에도 더 이상 줄일 수 없을 줄 알았던 코드이다. 해당 코드 제출 후에 일회성 변수 및 함수를 제거할 수 있는 부분을 파악하여 무려 41 B 를 더 줄이게 된다.
4차 Short
맞았습니다!!
w,x,y,z=map(int,input().split())
def g(i,j):m=max(abs(i),abs(j));return(2*m+i+j)*(1-2*(i<j))+1+4*m*m
for i in range(w,y+1):print(*[f'%{len(str(max(g(w,x),g(y,x),g(y,z))))}d'%g(i,j)for j in range(x,z+1)])2024년 8월 16일 19:38:37 제출시간 기준, 백준 1022번 모든 언어 카테고리 1등이 되었다. 쫄보라 백준에는 코드를 비공개하였지만 방문자 수 적은 내 블로그에 공개한다...
6. 반례모음
다음으로 풀이에 도움이 될만한 반례를 기술한다.
반례1
숫자 출력형식 오류 (우측 미정렬)
- 입력
-6 -6 5 1- 정답
145 144 143 142 141 140 139 138
146 101 100 99 98 97 96 95
147 102 65 64 63 62 61 60
148 103 66 37 36 35 34 33
149 104 67 38 17 16 15 14
150 105 68 39 18 5 4 3
151 106 69 40 19 6 1 2
152 107 70 41 20 7 8 9
153 108 71 42 21 22 23 24
154 109 72 43 44 45 46 47
155 110 73 74 75 76 77 78
156 111 112 113 114 115 116 117반례2
숫자 출력형식 오류 (우측 미정렬)
- 입력
-17 7 -15 10- 정답
1133 1132 1131 1130
1002 1001 1000 999
879 878 877 876반례3
숫자 출력형식 오류 (우측 미정렬)
- 입력
-17 -158 -15 -156- 정답
99998 98737 97484
99999 98738 97485
100000 98739 97486반례4
숫자 출력형식 오류 (우측 미정렬)
- 입력
-500 -499 -497 -499- 정답
1000000
996005
996006
996007반례5
메모리 초과, 시간 초과, 숫자 출력형식 오류 (우측 미정렬)
- 입력
-5000 -5000 -4998 -4998- 정답
100000001 100000000 99999999
100000002 99960005 99960004
100000003 99960006 99920017'Computer Science > Baekjoon' 카테고리의 다른 글
| [Baekjoon] 1262번 알파벳 다이아몬드 S1 <Short> (0) | 2024.09.22 |
|---|---|
| [Baekjoon] 15723번 n단 논법 S1 (0) | 2024.08.23 |
| [Baekjoon] 10101번 삼각형 외우기 B4 <Short> (1) | 2024.01.20 |
| [Baekjoon] 1068번 트리 G5 (0) | 2024.01.15 |
| [Baekjoon] 1193번 분수찾기 S5 <Short> (0) | 2023.12.22 |
