문제
무한히 큰 배열에 다음과 같이 분수들이 적혀있다.
| 1/1 | 1/2 | 1/3 | 1/4 | 1/5 | … |
| 2/1 | 2/2 | 2/3 | 2/4 | … | … |
| 3/1 | 3/2 | 3/3 | … | … | … |
| 4/1 | 4/2 | … | … | … | … |
| 5/1 | … | … | … | … | … |
| … | … | … | … | … | … |
이와 같이 나열된 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자.
X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다.
출력
첫째 줄에 분수를 출력한다.
기본 수학1이 정말 어렵다
브론즈 문제에 정답률도 높은데 접근을 못하겠다...
= 틀린 이유 =
블로그, 유튜브 등 이해하기 위해서 몇 시간 동안 해설 듣고 혼자 생각했다.
완벽하게 이해했다고 하기는 힘들지만 일단 작성한다.
이 문제는 규칙을 찾는게 제일 중요했다.
처음부터 규칙을 제대로 찾지 못했기 때문에 접근 조차 못했다.
= 해결 =
순방향, 역방향으로 이렇게 대각선 규칙을 찾는게 제일 중요했다.
첫번째 그룹 ) 1/1
두번째 그룹 ) 1/2, 2/1
세번째 그룹 ) 3/1, 2/2, 1/3
1/1 일 때 순방향, 1/2, 2/1일 때 역방향 이렇게 하나 하나 다 생각하면 된다.
내가 10번째 분수를 찾고 싶다고 가정해보자,
10을 입력하면 이 10은 몇 번째 그룹일까? 부터 찾아야 된다.
1 ) 몇 번째 그룹일까? = > 4번째 그룹,
2 ) 그 그룹에서 몇 번째 ? = > 내가 입력한 10 - 이전까지 그룹의 총 합 6 따라서 4
3 ) 순방향 ? 역방향? = > 역방향이기 때문에 4번째 값을 찾으면 된다.
참고로 첫번째 대각선에는 값이 1개, 두번째 대각선에는 2개, 세번째 대각선에는 3개 이 규칙도 알아둬야 한다.
1 ) crossCount가 1일 때 , 값 1개 / 2일 때, 값 2개 / 3일 때, 값 3개를 나타낼 수 있기 때문에
내가 원하는 10의 분수를 찾고 싶으면 그 이전까지 합을 계산해서 몇 번째 대각선에 10번째 값이 존재하는 지 알 수 있다.
2 ) n(n+1) / 2 수학 공식을 이용해서 그 행에서 몇 번째 값인지 구하는 과정이다.
3 ) 짝수일 때, 역방향으로 진행하기 때문에 분모가 더 큼을 이용해서 구한다.
아직 많이 부족하지만 더 열심히 해야겠다.
다른 사람이 푼 과정을 보고 여러가지 생각이 들지만... 그냥 내가 더 열심히 하자!
'백준 오답노트 > 기본 수학1' 카테고리의 다른 글
| 백준 - 기본 수학1 2775번 부녀회장이 될테야 / 구글로 해결 (0) | 2022.12.02 |
|---|---|
| 백준 - 기본 수학1 2869번 달팽이는 올라가고 싶다 / 구글로 해결 (0) | 2022.12.01 |
| 백준 - 기본 수학1 2292번 벌집 / 구글로 해결 (0) | 2022.11.30 |
