1193번 분수찾기 문제
생각
처음 시도한 방법 : 칸을 생각하지 않고 분자와 분모의 규칙성을 찾아내서
1 - 1 - 2 - 3 - 2 - 1 - 1 - 2 - 3 - 4 - 5 - 4 - 3 - 2 – 1 - 1– 2 – 3 – 4 – 5 – 6 – 7 – 6 – 5 – 4 – 3 – 2 - 1
분자 A 규칙 : 1 + 2의 기준 패턴으로 계속 더해졌다 빼졌다 반복
1 – 2 – 1 – 1 – 2 – 3 – 4 – 3 – 2 – 1 – 1 – 2 – 3 – 4 – 5 – 6 – 5 – 4 – 3 – 2 - 1
분모 규칙 : 0 + 2의 기준 패턴으로 계속 더해졌다 빼졌다 반복
이러한 패턴을 알게 돼서 구현만 하면 될줄 알았는데 나중에 확인해보니 시간제한이 0.5초였다.
또 내가 수학적 생각을 안하고 무대포로 풀 생각만 했구나 싶었다.
결과적으로 저렇게 연산을 했을 때 시간이 부족해서 필히 문제가 생겼을 것이다.
아무리 생각해도 정확한 정답이 나오지 않아 결국 다른 분들의 풀이를 봤다.
-------
hint
이걸 보면서 규칙성 확인
-------
Solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | import java.util.Scanner; public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = Integer.parseInt(sc.nextLine()); int a = 0; int count = 1; int b = 0; int tmp = 0; int mother, child; while(true) { if( a >= n ) { b = a - n - 1; mother = n - tmp; child = count - mother; if(child < 0) { child *= -1; } child = count - mother; if(count % 2 == 1) { System.out.println(mother + "/" + child); } else { System.out.println(child + "/" + mother); } break; } tmp = a; a += count; count++; } } } // 2 3 4 5 6 7 8 //1 3 6 10 15 21 28 36 | cs |
실행시간 - 224ms
위의 hint그림 처럼 대각선 기준으로 정방향 역방향으로 1부터 순차증가가 된다.
이 부분을 체크해서 각 대각라인 별 갯수가 1 - 3 - 6 - 10 - 15 - 21 순으로 증가하는데,
a(0) = a + 대각라인 으로 총 갯수를 파악 가능하며,
child / mother라 했을 때 mother = n - tmp로 해당 번호의 순번, 즉 분자나 분모의 값 하나를 구할 수 있고
이후 count - mother를 통해 다른 분자나 분모의 값을 구할 수 있다.
count - mother가 가능한 이유는 각 대각라인 순번별로 2부터 시작해 합이 1씩 증가한다. 그 합은 child + mother 이다.
---
수학 문제는 난이도가 쉽게 나와도 정말 풀기 어려운 듯 하다 최적화를 떠나서 구현 자체가 너무 힘듦
이후에도 해당 문제는 계속 들여다볼 것 같다.
'공부 > Algorithm' 카테고리의 다른 글
| 백준 2292번 벌집 자바로 풀어 본 짧은 글 (0) | 2022.12.20 |
|---|---|
| 백준 1712번 손익분기점 자바로 풀어 본 짧은 글 (0) | 2022.12.20 |
| 백준 2869번 달팽이는 올라가고 싶다 자바로 풀어 본 짧은 글 (0) | 2022.12.18 |
| 백준 2204번 도비의 난독증 테스트 자바로 풀어 본 짧은 글 (0) | 2022.12.18 |
| 백준 4447번 좋은놈 나쁜놈 자바로 풀어 본 짧은 글 (0) | 2022.12.18 |