알고리즘/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);
  } 
}