반응형
https://www.acmicpc.net/problem/1193
1193번: 분수찾기
첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다.
www.acmicpc.net
import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int X = sc.nextInt(); int cnt = 0; boolean flag = false; //짝수 분자 증가(위,아래) , 홀수 분자 감소(아래,위) for(int i=1; i <= 10000000; i++){ if(flag) return; cnt += i; if(cnt >= X){ cnt -= i; int a = 1; int b = i; while(true){ cnt++; if(cnt == X){ if(i % 2 ==0){ System.out.println("" + a + "/" + b); }else{ System.out.println("" + b + "/" + a); } flag = true; return; }else{ a++; b--; } } } } } }
1. 풀이

규칙을 먼저 찾아야 한다. 규칙은 대각선방향으로 순서대로 움직임
1 : 1/1
2 : 1/2 , 2/1
3 : 3/1, 2/2, 1/3
4 : 1/4, 2/3, 3/2, 4/1
.........
짝수는 위에서 아래로 홀수그룹은 아래에서 위로 움직이게 된다.
1. 어떤그룹인지 먼저 찾는다.
- 1부터 ~ 10000000 까지 loop 돌면서 합이 X와 크거나 같은 그룹을 찾는다.
2. 같은 그룹을 찾게 되면 해당 그룹을 loop 돌면서 입력받은 값과 같은 번호를 찾는다.
- a 는 1번부터 증가, b는 그룹 번호 부터 감소시켜 나간다.
- 홀수는 b/a 짝수는 a/b 로 출력한다.
반응형
'기타 > 알고리즘' 카테고리의 다른 글
[알고리즘] 백준 1138 한줄로 서기 실버2 Java (0) | 2023.09.07 |
---|---|
[알고리즘] 프로그래머스 - 짝지어제거하기 Lv02 Java (0) | 2023.07.18 |
[알고리즘] 프로그래머스 - 멀리뛰기 Java Lv02 (0) | 2023.07.15 |
[알고리즘] 프로그래머스 - 숫자의표현 Lv02 Java (0) | 2023.07.13 |
[알고리즘] 프로그래머스 - 최소값만들기 Lv02 Java (0) | 2023.07.04 |