[실버5] 1193. 분수찾기 (Java)

https://www.acmicpc.net/problem/1193

1193번: 분수찾기

점점 아주 조금씩이지만 익숙해져 가는게 느껴지네요. A+B도 틀렸었는데,, 감격..

---

 해당 문제는 지그재그 순서로 배열을 탐색하는 문제로,  아래의 표와 예시를 통해 이해하시는게 더 빠를 것 같습니다!

 

 위와 같이 각 배열 원소에 분수를 가지고 있으며 파란색 번호 순서에 맞추어 탐색을 진행하며, 입력 받은 숫자에 해당하는 위치에 있는 분수를 출력하는 문제입니다. 혹시 이해가 안된다면 아래의 입력(Input) 과 출력(Output) 예시를 참고 부탁드리겠습니다. 

Example :

Input : 1 = > Output : 1 / 1

Input : 2 = > Output : 1 / 2

Input : 3 = > Output : 2 / 1

Input : 4 = > Output : 3 / 1

Input : 5 = > Output : 2 / 2

Input : 6 = > Output : 1 / 3

Input : 7 = > Output : 1 / 4

Input : 8 = > Output : 2 / 3

...

---

 문제에선 분수로 설명하였지만, 저같은 경우 분수로 보지 않고 '/' 기준 왼쪽을 X, 오른쪽을 Y로 놓고 생각하여 풀었습니다. 

코드 작성 전, 아래와 같이 솔루션을 정리하였습니다.

▶ 대각선의 끝에 도달 시, 다음 대각선으로 이동.

▶ 배열의 [0][0]위치를 1번 대각선으로 정의 후, 홀수번째 대각선은 X=1,Y= 해당 대각선의 길이 부터, X++, Y--

▶ 배열의 [0][0]위치를 1번 대각선으로 정의 후, 짝수번째 대각선은 X=해당 대각선의 길이 ,Y = 1부터 X--, Y++

▶ 입력한 곳에 도달 시 멈추고 X/Y 출력

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.OutputStreamWriter;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int nTarget = Integer.parseInt(st.nextToken());
		
		int X = 1;
		int Y = 1;
		
		// 1일 경우 return;
		if(nTarget == 1) {
			bw.write(X + "/" + Y);
			bw.flush();
			bw.close();
			return;
		}

		int nIndex = 1;	// 각 대각선의 순서
		int nNum = 1; 	// 각 대각선의 길이
		int nCount = 1; // N번째 분수
		
		while(nCount < nTarget) {
			if(nIndex == nNum) {
				nIndex = 1;
				nNum++;
				if(nNum % 2 == 0) {
                	// 짝수 번째 대각선 첫번째 값
					X = 1;
					Y = nNum;
				}
				else {
                	// 홀수 번째 대각선 첫번째 값
					X = nNum;
					Y = 1;
				}
			}
			else if(nNum % 2 == 0) { // 짝수 번째 대각선
				X++;
				Y--;
				nIndex++;
			}
			else if(nNum % 2 == 1) { // 홀수 번째 대각선
				X--;
				Y++;
				nIndex++;
			}
			nCount++;
		}
		
		bw.write(X + "/" + Y);
		bw.flush();
		bw.close();
	}
}

 스터디 팀원과의 공유를 위해서 조금 더 자세하게 적도록 노력하였습니다. 모르고리즘 화이팅(?!)

긴 글 읽어주셔서 감사합니다!

Good Luck! (피드백 고맙습니다)