[백준] 1193번 : 분수찾기- Java(자바)

이번 문제는 분수를 찾는 문제였습니다. 앞으로는 문제를 이해한 상태라고 가정하고 설명하도록 하겠습니다.

Step 0 . 해답 코드

import java.util.Scanner;
public class Fraction_1193 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int sum = 0; //입력 받은 숫자가 어느 줄에 위치해 있는지 찾을 때 사용
		int x = sc.nextInt();
		int a, b = 0;//최종적으로 출력해줄 좌변 우변?   .. a/b
		for (int i = 0; i < 4472; i++) { //X의 범위 천만은 4472까지 범위 지정하면 다 받을 수 있음.
			sum = sum + (i + 1);
			if (sum >= x) {
				int sum_bef = sum - (i + 1); //계산을 위해 현재 sum의 전의 값을 구해줌.
				a = x - sum_bef; //입력 값 - 전의 sum값을 해주면 입력 값이 몇 번째 위친지 알 수 있음.
				b = (i + 1) - (a - 1);
				if ((i + 1) % 2 == 0) { //짝수 칸이면 위>아래
					System.out.println(a + "/" + b);
					break;
				} else { //홀수 칸이면 아래> 위
					System.out.println(b + "/" + a);
					break;
				}
			}
		}
		
	}

}

이번 문제에서는 분수의 값을 찾기 위해서 for, if문과 간단한 수식 몇 가지를 사용했습니다.

Step 1. 문제 접근

우선 문제를 봐보면 분수들이 대각선으로 1개씩 증가하는 것을 볼 수 있습니다.총 개수는 1 > 3 > 6 > 10 > 15 > 21 이런식으로 2, 3, 4, 5..씩 증가하는 것을 볼 수 있습니다. 그렇기에 저희가 찾는 X의 값이 어느 위치에 있는지 알 수 있다면 쉽게 풀 수 있습니다. 크게 문제를 푸는 방향은 1.입력 받은 숫자가 몇 번째 속하는가? 2.해당 숫자는 짝수 줄인가 홀수 줄인가? 3.지금까지 모은 정보로 원하는 숫자 찾기. 순으로 진행하였습니다.

Step 2. 문제 해결

1. 입력받은 숫자는 어느 줄에 위치하는가?

• 몇 번째 줄인지를 알면 해당 수의 범위등을 알 수 있어 유용한 정보를 얻을 수 있습니다.

  for (int i = 0; i < 4472; i++) { //X의 범위 천만은 4472까지 범위 지정하면 다 받을 수 있음.
  			sum = sum + (i + 1);
  			if (sum >= x) {

  sum의 값은 해당 줄의 맥시멈 숫자입니다. 예를 들어 첫 줄은 1, 두 번째 줄은 3, 다음은 6, 10, 15, 21... 이렇습니다. 이제 이 수를 들고 for문을 4472번 돌려서(문제에서 X의 값은 천만까지로 정해져 있고 sum값을 저렇게 계속 더하면 결국 4472번 돌리면 그 범위를 딱 충족하기에 저만큼 돌렸습니다. 무한 반복으로 간단하게 처리하여도 될 거 같습니다.) 저희가 찾아야 할 숫자가 어느 범위에 속하는지를 구해줍니다. 해당 숫자가 처음 조건을 만족하는 경우를 if문을 통해 구해주고 끝에 break문을 통해 프로그램이 한 번만 작동하도록 하였습니다.

2. 해당 숫자는 짝수 줄인가 홀수 줄인가?

• 이 문제는 숫자를 지그재그로 구하기 때문에 짝수 줄 혹은 홀수 줄에 위치한지에 따라 숫자 카운팅 방법이 달라집니다. (프로그램에서는 sum_bef, a ,b등의 해답을 구하는 과정 다음에 짝 홀을 찾지만 논리 순서는 짝홀을 찾은 후에 해답을 찾으므로 논리 순서대로 코드 순서를 살짝 바꿔서 설명드렸습니다.)

if ((i + 1) % 2 == 0) {
}
else {
}

나머지 연산자 %를 사용해서 짝 홀수를 나눠줬습니다.

3. 지금까지의 정보로 정답을 구하자.

• 지금까지의 정보를 토대로 정답을 구했습니다.

if (sum >= x) {
				int sum_bef = sum - (i + 1); //계산을 위해 현재 sum의 전의 값을 구해줌.
				a = x - sum_bef; //입력 값 - 전의 sum값을 해주면 입력 값이 몇 번째 위친지 알 수 있음.
				b = (i + 1) - (a - 1);
				if ((i + 1) % 2 == 0) { //짝수 칸이면 위>아래
					System.out.println(a + "/" + b);
					break;
				} else { //홀수 칸이면 아래> 위
					System.out.println(b + "/" + a);
					break;
				}
			}
		}

sum의 위치를 if로 구해주고 현재 칸 전의 sum값을 sum_bef에 저장해주었습니다. 그 다음 sum_bef를 사용해서 a 값을 구하고 a를 이용해서 b 값을 구해줬습니다. 여기서 a b값은 저희가 마지막에 구할 정답의 a / b형태에서 좌 우변의 값들입니다. 수식은 숫자들을 보고 제가 직접 짰는데 어렵지 않아서 좀 보다 보면 여러 가지 방법으로 만들 수 있을 것으로 생각됩니다.
그 후 a b 값들은 짝수일 경우는 a / b형태로, 홀수일 경우는 b / a 형태로 출력해고 프로그램이 종료하도록 하기 위해 break문을 사용했습니다.

Step 3. 배우고 느낀 점

문제 자체는 어렵지 않아 1~20분정도로 쉽게 푼 문제였습니다. 수식도 어렵지 않아서 재밌게 성취감을 느낄 수 있었던 문제였습니다. 이번 문제에서는따로 프로그래밍적인 능력의 향상 보다는 얼마 전부터 사용하던 노트에 우선 필기해서 정리하고 푸는 방법의 틀을 잡은거 같았습니다. 노트로 어떤 방식으로 풀지 정하고 써서 풀어보니 훨씬 쉽고 정리도 쉬웠습니다. 아마 그냥 박치기 식으로 이클립스를 띄워두고 풀었다면 2~3시간도 넘게 걸렸지 싶습니다. 역시 정직하게 돌아가는 방법이 제일 빠른 방법인거 같습니다.

출처 : 백준 1193번 https://www.acmicpc.net/problem/1193