99클럽 코테 스터디 25일차 TIL + 자릿수 반올림

TIL

정사각형 모양의 분수 모양 데이터가 있는 경우, 대각선으로 잘라서 (분모 + 분자) 데이터의 합을 패턴으로 사용할 수 있다.

T : (분모 + 분자) 데이터의 합
X : 알고자하는 순서(입력 값)
sum : 칸 수의 합(T의 합)

지그재그 순서로 번호를 매기기 때문에 분모/분자의 방향이 서로 다른 점을 유의한다.

 T가 홀수인 경우, (오른쪽위->왼쪽아래 방향)
 T가 짝수인 경우, (왼쪽아래->오른쪽위 방향)

 

[T 홀수]

- 분자 : (T - (X - sum - 1)

- 분모 : (X - sum)

 

[T 짝수]

- 분자 : (X - sum)

- 분모 : (T - (X - sum - 1)

 

분자/분모의 값이 서로 반대임을 알 수 있다.

 

+++

추가적으로, X의 값이 대각선 범위 내에 접근하고 있어야하므로

(X <= T+sum) 인 경우에만 분자/분모 값을 확인한다.

 

그 외는 T, sum 값을 변경하면서 대각선 범위 내에 접근할 수 있도록 한다.

 

회고

구현 문제에서 패턴을 찾기 위해서는 다양한 문제를 많이 풀어보고, 이해하는 것이 중요함을 느꼈다.

---

백준

1193: 분수찾기

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

1193번: 분수찾기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int X = Integer.parseInt(br.readLine());
    int T = 1, sum = 0;

    while (true) {
      if (X <= T + sum) {
        // 대각선 범위 내로 접근할 경우
        if (T % 2 == 1) { // T가 홀수인 경우, (오른쪽위->왼쪽아래 방향)
          // 분자 (T - (X - sum - 1)
          // 분모 (X - sum)
          System.out.println((T - (X - sum - 1) + "/" + (X - sum)));
          break;
        }
        else { // T가 짝수인 경우, (왼쪽아래->오른쪽위 방향)
          // 분자 (X - sum)
          // 분모 (T - (X - sum - 1)
          System.out.println((X - sum) + "/" + (T - (X - sum - 1)));
          break;
        }
      }
      else {
        // 대각선 범위 내가 아닐 경우
        sum += T;
        T++;
      }
    }
  }
}

---

참고

https://st-lab.tistory.com/74

[백준] 1193번 : 분수찾기 - JAVA [자바]

 

---

99클럽 1기를 수강하면서 작성한 글입니다.

https://99club.oopy.io/

99클럽 스터디원 모집 중