백준 1193번 분수찾기 자바 java

문제

풀이

처음에 문제를 보았을 땐 지그재그 순서를 이해를 못했다

2/1 -> 3/1 으로 왜 이쪽으로 이동을 하지? 라는 생각에 시간을 많이 소비했다

지그재그 순서로 이동하는 경로

대각선으로 이동

대각선으로 ↙ (빨간선) 이동하는 것을 보면 1/2 -> 2/1, 1/4 -> 2/3 -> 3/2 -> 4/1

i / j 이면 i + 1 / j - 1로 값이 변경이 된다

대각선으로 ↗ (파란선) 이동하는 것을 보면 3/1 -> 2/2 -> 1/3, 5/1 -> 4/2 -> 3/3 -> 2/4 -> 1/5

i / j 이면 i - 1 / j + 1 로 값이 변경이 된다

아래, 우측으로 이동

→ 우측으로 이동하는 경우 (빨간선)는 ↗ 방향으로 이동이 안될 때

i / j 이면 i의 값이 0이 된다면 우측으로 이동하게 처리

↓ 아래로 이동하는 경우 (파란선)는 ↙ 방향으로 이동이 안될 때

i / j 이면 j의 값이 0이 된다면 아래로 이동하게 처리

코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int x = sc.nextInt();
        int count = 1;
        int i = 1;
        int j = 1;
        boolean downSearch = false;
        boolean upSearch = false;

        while (x != count) {
            //System.out.printf("%d/%d : %d\n", i, j, count);

            if (downSearch) {
                if (j - 1 == 0) {
                    downSearch = false;
                    continue;
                } else {
                    i += 1;
                    j -= 1;
                    count++;
                    continue;
                }
            }

            if (upSearch) {
                if (i - 1 == 0) {
                    upSearch = false;
                    continue;
                } else {
                    i -= 1;
                    j += 1;
                    count++;
                    continue;
                }
            }

            if (i == 1) {
                j += 1;
                count++;
                downSearch = true;
                continue;
            } else if (j == 1) {
                i += 1;
                count++;
                upSearch = true;
                continue;
            }

        }

        System.out.printf("%d/%d", i, j);
    }
}

 

출처

www.acmicpc.net/problem/1193