안녕하세요. 지난 포스팅의 BOJ 2292번 : 벌집에서는 계차수열을 활용해서 문제를 풀어보았습니다. 오늘도 역시 수열과 관련된 문제를 풀어보도록 하겠습니다.
완벽한 코딩은 존재하지 않습니다. 제가 제출한 코드 역시 마찬가지고 그저 참고만 해주시길 바랍니다.
핵심 포인트
- 그룹 수열(Group Sequence)
제출 코드
X = int(input())
G = 1
while (G * (G - 1)) // 2 < X :
G += 1
G = G - 1
N = X - (G * (G - 1)) // 2
if G % 2 == 0 : print(str(N) + '/' + str(G - N + 1))
else : print(str(G - N + 1) + '/' + str(N))
해설
사실 이 문제는 그룹 수열 자체를 이해하는 것이 중요한게 아니라 얼마나 규칙성을 잘 찾는 지가 중요합니다. 일단, 문제를 분석해보면 어떤 $X$가 주어졌을 때 규칙에 맞게 분수를 배열했을 때 $X$번째 분수를 찾는 것이 목표입니다. 각 분수를 배열해보면 아래와 같습니다.
$$\frac{1}{1}, \frac{1}{2}, \frac{2}{1}, \frac{3}{1}, \frac{2}{2}, \frac{1}{3}, \frac{1}{4}, \frac{2}{3}, \frac{3}{2}, \frac{4}{1}, \dots $$
이렇게 보면 딱히 규칙성이 없어보이네요. 따라서 아래와 같이 격자를 표시해보겠습니다.
$$\frac{1}{1} | \frac{1}{2}, \frac{2}{1} | \frac{3}{1}, \frac{2}{2}, \frac{1}{3} | \frac{1}{4}, \frac{2}{3}, \frac{3}{2}, \frac{4}{1} | \dots $$
이제 저희는 각 격자별로 1번 그룹, 2번 그룹, 3번 그룹, 4번 그룹, ... $G$번 그룹이라고 하겠습니다. 따라서 목표는 $X$번째 분수가 $G$번째 분수 그룹의 몇 번째 분수인지 확인하는 것으로 바뀝니다. 따라서 두 가지 단계로 이 문제를 풀 수 있을 거 같습니다.
STEP1. 해당 분수가 몇 번째 그룹($G$)에 속하는 지 찾기
일단, $X$가 주어졌다고 가정하겠습니다. 그렇다면 $X$번째 분수가 몇 번째 그룹에 속하는 지 확인하기 위해서는 어떻게 해야할까요? 방법은 간단합니다. $X$의 의미가 무엇인지를 다시 생각해보도록 하죠. $X$란 $X$번째 분수가 속한 그룹보다 작은 모든 그룹들이 속한 분수들의 개수의 합보다는 작아야합니다. 이때, $G$번째 그룹은 $G$개의 분수가 속한다는 것을 인지하신다면 아래와 같은 부등식을 얻을 수 있습니다.
$$1 + 2 + \cdots + (G - 1) = \frac{G(G - 1)}{2} < X$$
위 부등식을 만족하는 $G$는 여러 개가 있을 수 있습니다. 그 중에서 가장 큰 $G$가 $X$번째 분수가 속한 그룹의 바로 이전 그룹이 될 것입니다. 이를 저는 위 코드에서 while 문을 이용해서 구현하였습니다. 그 다음에 $G$에서 1을 빼게 되는 데 이는 $\frac{G(G - 1)}{2} < X$를 만족하지 않으면 종료됩니다. 그 순간 $G$에 1이 더해지기 때문에 저희가 원하는 값이 나오지 않아 1을 빼주는 것 입니다.
STEP2. 해당 그룹($G$)에서 몇 번째 분수($N$)인지 찾기
$X$번째 분수가 어떤 그룹에 속하는 지 알았다면 해당 그룹에서 몇 번째 분수인지 알아봐야합니다. 이는 아주 간단합니다. 다만, $G$가 짝수인지 홀수인지에 따라서 나뉘게 됩니다.
- $G$가 짝수인 경우 : $\frac{1}{G}, \frac{2}{G - 1}, \frac{3}{G - 2}, \dots, \frac{N}{G - N + 1}, \dots, \frac{G}{1}$
- $G$가 홀수인 경우 : $\frac{G}{1}, \frac{G - 1}{2}, \frac{G - 2}{3}, \dots, \frac{G - N + 1}{G}, \dots, \frac{1}{G}$
그러므로 저희는 $G$가 짝수일 때는 $\frac{N}{G - N + 1}$을 출력하면 되고 $G$가 홀수일 때는 $\frac{G - N + 1}{G}$를 출력하면 됩니다. 그렇다면 $N$을 알아야겠네요. 이 역시 간단하죠. $\frac{G(G - 1)}{2}$이 $X$가 속한 그룹($G$)보다 작은 모든 그룹의 분수들의 개수의 전체 합이라면 $X - \frac{G(G - 1)}{2}$는 남은 분수의 개수이므로 이 값이 $N$이 됩니다.
참고자료 및 그림출처
'Programming > Coding Problem' 카테고리의 다른 글
BOJ 10250번 : ACM 호텔 (0) | 2022.07.10 |
---|---|
BOJ 2869번 : 달팽이는 올라가고 싶다 (0) | 2022.07.09 |
BOJ 2292번 : 벌집 (0) | 2022.07.06 |
BOJ 1712번 : 손익분기점 (0) | 2022.07.05 |
BOJ 1316번 : 그룹 단어 체커 (0) | 2022.07.04 |
안녕하세요. 지난 포스팅의 BOJ 2292번 : 벌집에서는 계차수열을 활용해서 문제를 풀어보았습니다. 오늘도 역시 수열과 관련된 문제를 풀어보도록 하겠습니다.
완벽한 코딩은 존재하지 않습니다. 제가 제출한 코드 역시 마찬가지고 그저 참고만 해주시길 바랍니다.
핵심 포인트
- 그룹 수열(Group Sequence)
제출 코드
X = int(input())
G = 1
while (G * (G - 1)) // 2 < X :
G += 1
G = G - 1
N = X - (G * (G - 1)) // 2
if G % 2 == 0 : print(str(N) + '/' + str(G - N + 1))
else : print(str(G - N + 1) + '/' + str(N))
해설
사실 이 문제는 그룹 수열 자체를 이해하는 것이 중요한게 아니라 얼마나 규칙성을 잘 찾는 지가 중요합니다. 일단, 문제를 분석해보면 어떤 $X$가 주어졌을 때 규칙에 맞게 분수를 배열했을 때 $X$번째 분수를 찾는 것이 목표입니다. 각 분수를 배열해보면 아래와 같습니다.
$$\frac{1}{1}, \frac{1}{2}, \frac{2}{1}, \frac{3}{1}, \frac{2}{2}, \frac{1}{3}, \frac{1}{4}, \frac{2}{3}, \frac{3}{2}, \frac{4}{1}, \dots $$
이렇게 보면 딱히 규칙성이 없어보이네요. 따라서 아래와 같이 격자를 표시해보겠습니다.
$$\frac{1}{1} | \frac{1}{2}, \frac{2}{1} | \frac{3}{1}, \frac{2}{2}, \frac{1}{3} | \frac{1}{4}, \frac{2}{3}, \frac{3}{2}, \frac{4}{1} | \dots $$
이제 저희는 각 격자별로 1번 그룹, 2번 그룹, 3번 그룹, 4번 그룹, ... $G$번 그룹이라고 하겠습니다. 따라서 목표는 $X$번째 분수가 $G$번째 분수 그룹의 몇 번째 분수인지 확인하는 것으로 바뀝니다. 따라서 두 가지 단계로 이 문제를 풀 수 있을 거 같습니다.
STEP1. 해당 분수가 몇 번째 그룹($G$)에 속하는 지 찾기
일단, $X$가 주어졌다고 가정하겠습니다. 그렇다면 $X$번째 분수가 몇 번째 그룹에 속하는 지 확인하기 위해서는 어떻게 해야할까요? 방법은 간단합니다. $X$의 의미가 무엇인지를 다시 생각해보도록 하죠. $X$란 $X$번째 분수가 속한 그룹보다 작은 모든 그룹들이 속한 분수들의 개수의 합보다는 작아야합니다. 이때, $G$번째 그룹은 $G$개의 분수가 속한다는 것을 인지하신다면 아래와 같은 부등식을 얻을 수 있습니다.
$$1 + 2 + \cdots + (G - 1) = \frac{G(G - 1)}{2} < X$$
위 부등식을 만족하는 $G$는 여러 개가 있을 수 있습니다. 그 중에서 가장 큰 $G$가 $X$번째 분수가 속한 그룹의 바로 이전 그룹이 될 것입니다. 이를 저는 위 코드에서 while 문을 이용해서 구현하였습니다. 그 다음에 $G$에서 1을 빼게 되는 데 이는 $\frac{G(G - 1)}{2} < X$를 만족하지 않으면 종료됩니다. 그 순간 $G$에 1이 더해지기 때문에 저희가 원하는 값이 나오지 않아 1을 빼주는 것 입니다.
STEP2. 해당 그룹($G$)에서 몇 번째 분수($N$)인지 찾기
$X$번째 분수가 어떤 그룹에 속하는 지 알았다면 해당 그룹에서 몇 번째 분수인지 알아봐야합니다. 이는 아주 간단합니다. 다만, $G$가 짝수인지 홀수인지에 따라서 나뉘게 됩니다.
- $G$가 짝수인 경우 : $\frac{1}{G}, \frac{2}{G - 1}, \frac{3}{G - 2}, \dots, \frac{N}{G - N + 1}, \dots, \frac{G}{1}$
- $G$가 홀수인 경우 : $\frac{G}{1}, \frac{G - 1}{2}, \frac{G - 2}{3}, \dots, \frac{G - N + 1}{G}, \dots, \frac{1}{G}$
그러므로 저희는 $G$가 짝수일 때는 $\frac{N}{G - N + 1}$을 출력하면 되고 $G$가 홀수일 때는 $\frac{G - N + 1}{G}$를 출력하면 됩니다. 그렇다면 $N$을 알아야겠네요. 이 역시 간단하죠. $\frac{G(G - 1)}{2}$이 $X$가 속한 그룹($G$)보다 작은 모든 그룹의 분수들의 개수의 전체 합이라면 $X - \frac{G(G - 1)}{2}$는 남은 분수의 개수이므로 이 값이 $N$이 됩니다.
참고자료 및 그림출처
'Programming > Coding Problem' 카테고리의 다른 글
BOJ 10250번 : ACM 호텔 (0) | 2022.07.10 |
---|---|
BOJ 2869번 : 달팽이는 올라가고 싶다 (0) | 2022.07.09 |
BOJ 2292번 : 벌집 (0) | 2022.07.06 |
BOJ 1712번 : 손익분기점 (0) | 2022.07.05 |
BOJ 1316번 : 그룹 단어 체커 (0) | 2022.07.04 |