알고리즘/Java
[백준] 1193번 분수찾기
ewok
2023. 2. 11. 19:34
https://www.acmicpc.net/problem/1193
1193번: 분수찾기
첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다.
www.acmicpc.net
움직임을 x, y 좌표평면으로 표현할 수 있다.
오른쪽 한칸 : y가 1 증가 (0, +1)
아래로 한칸 : x가 1 증가 (+1, 0)
좌하단으로 한 칸 : x가 1 증가, y가 1 감소 (+1, -1)
우상단으로 한칸 : x가 1 감소, y가 1 증가 (-1, +1)
시작 위치는 1/1로 (1,1)로 표시할 수 있다. 움직이는 방향을 표시하기 위해 mx, my 변수를 사용하여 위 움직임에 해당하는 값을 대입했다. 처음에는 우상단으로 움직이게 했으며(이를 위해 mx에는 -1, my에는 1을 초기값으로 주었다.)
좌표평면 범위(x>=1, y>=1)를 벗어나면 우상단으로 움직이는 대신 오른쪽으로 이동하도록 했다. 그리고 이 경우 이제 좌하단으로 움직여야 하므로 mx와 my값을 각각 1, -1로 변경했다.
이러한 과정을 순서도로 표현하면 아래와 같다.
java 코드
더보기
import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int x = 1;
int y = 1;
int mx = -1;
int my = 1;
for(int i=1; i<n; i++) {
if(mx == -1 && my == 1) {
x -= 1;
y += 1;
if(x<1 || y<1) {
x += 1;
mx = 1;
my = -1;
}
} else {
x += 1;
y -= 1;
if(x<1 || y<1) {
y += 1;
mx = -1;
my = 1;
}
}
}
System.out.println(x+"/"+y);
}
}