이 글의 목적?
점점 난이도가 올라가고 있는 것 같은 느낌이든다. 벌집 문제 푼지 얼마나 되었다고 바로 다음 문제부터 막히는건지...🫠
이 문제를 처음 읽고나서는 2차원 배열이라고 가정하고 각 요소의 행과 열 위치 인덱스 값을 더하고 곱하고 나누고 빼면서 머리를 쥐어짜며 규칙을 찾고자 했다. (아무래도 이미지를 보고 배열로 풀어야한다는 의식이 컸던것 같다 😭)
하지만 결국 규칙을 찾지 못했고, 구글링으로 풀이를 찾아낼 수 밖에 없었다. 단, 풀이만 참고하고 코드는 직접 작성했다. (이것만은 양보못한다!!)
문제
무한히 큰 배열에 다음과 같이 분수들이 적혀있다.
이와 같이 나열된 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자.
X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.
풀이
막상 풀이를 생각하면 간단하다. 하단의 이미지처럼 분모와 분자의 합(T)이 공통된 위치별로 그룹화하여 대각선 단위로 살펴보면 된다.
그리고 각 대각선별 분수의 개수도 보면 분모와 분자의 합(T)에서 하나를 뺀 수라는 것을 확인할 수 있다. 또한 분모와 분자의 합(T)이 홀수이냐 짝수이냐에 따라 읽는 순서가 달라지는 것도 알 수 있다.
정리하자면 다음과 같다.
- 분모와 분자의 수의 합 (T)
- 각 그룹별 분수의 수 (T-1)
- 읽는 방향 (T가 홀수면 ↙️ / T가 짝수면 ↗️)
코드로 옮길 때의 중점사항은 다음과 같다.
- 순차적으로 그룹별 분수의 개수를 더해나간다.
- 주어진 X가 순차적으로 더한 분수의 개수의 크기보다 작을 경우의 그룹을 찾는다.
- 주어진 그룹의 값들을 나열하고 읽는 방향을 신경쓰며 X번째 분수를 찾는다.
이 글의 레퍼런스
세상을 현명하게 이끌어갈 나의 성장 일기 📓