[백준] 1193번: 분수찾기

 

이번 문제는 백준 난이도 실버5 '분수찾기' 문제이다.

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

 

문제의 조건은 나와있는 그림의 분수처럼 위치해 있는 2차원 배열맵에서 지그재그로 이동해야한다.

→  그림으로 표현하면 이런 식으로 이동한다는 뜻이다.

 

그런데 맵을 자세히 보면 분수형태로 표현되어있지만 이건 곧 원소의 위치를 나타내는 것이기도 하다.

→  행/열 형태.

 

즉, 2차원 맵을 지그재그로 이동하며 이동 시마다 값이 1씩 증가하게 되는 규칙을 따른다. 그렇게 한 숫자를 입력했을 때 해당 숫자가 위치한 행/열 주소를 출력하는 문제다.

 

규칙을 보면 대각선으로 이동하며 각 각 층으로 나눠 표시할 수 있을 것 같다.

이런식으로

그리고 층이 증가할 수록 해당 층의 원소 갯수가 1씩 증가한다.

Ex) 1층 : 1개, 2층 : 2개, 3층 : 3개 ... n층 : n개

→ 1개, 2개, 3개 ... n개 의 규칙이 생긴다.

 

여기서 우리는 누적합 공식을 이용해 문제를 해결할 수 있다.

입력값 X가 주어지고 각 층별의 원소 갯수 값을 누적해서 더한다.

예로 X가 14라고 한다면

누적합 : 1 + 2 + 3 + 4 + 5 = 15 이렇게 1층 2층 3층 4층 5층까지의 원소 갯수들을 차례차례 더하면 15라는 값이 나오고

이 값은 입력값인 X 14보다 커지니 X는 15값인 5층에 존재한다.

→ 4층은 최대 크기가 10이기 때문에 14는 들어갈 수 없기 때문

 

즉 이 상태에서 입력값 X에 이전 층의 마지막 인덱스인 10 (4층 원소 구간 : 7 ~ 10)을 빼주면

5층에서의 입력값 위치를 알 수 있다. 

 

여기서 X - 4층의 누적합을 빼면 5층에서 4번째 원소가 입력값의 분수값(주소)임을 알 수 있다.

 

이제 코드로 과정을 나타내보자

---

 

[Python]

 

입력값 X를 받은 후,

우선 층을 나타내는 layer변수, 누적합을 저장하는 sum이란 변수를 생성한다.

X가 sum보다 클 때까지 반복을 한다. 

결론적으로 X가 14라면 layer는 5이고 누적합은 15가 된다. 

X = int(input())

layer = 1
sum = 1
while X > sum:
    layer += 1
    sum += layer

 

여기서 ※ 현재 층의 위치를 계산하기 위해 누적합에 현재 층 5의 값을 빼준다.

15 - 5 = 10

sum -= layer

 

if layer % 2 == 0:
    top = X - sum
    bottom = layer - (X - sum) + 1
else:
    top = layer - (X - sum) + 1
    bottom = X - sum

 

대각선을 지그재그로 이동하기 때문에 문제의 조건에 따라 첫원소 이후 오른쪽 원소부터 이동을 시작하며 지그재그로 이동한다.

그러면 짝수 layer일 때는 대각선 윗방향, 홀수 layer일 때는 대각선 아래방향으로 이동한다는 규칙을 찾을 수 있다.

 

대각선 윗방향(짝수)일 때는 분모가 커지고 분자가 작아진다.

대각선 아랫방향(홀수)일 때는 반대이다.

조건에 맞춰 layer - (X - sum) + 1과  X - sum의 식을 통해 분수값을 구한다.

 

<전체코드>

X = int(input())

layer = 1
sum = 1
while X > sum:
    layer += 1
    sum += layer

sum -= layer

if layer % 2 == 0:
    top = X - sum
    bottom = layer - (X - sum) + 1
else:
    top = layer - (X - sum) + 1
    bottom = X - sum

print(f"{top}/{bottom}")

출력 결과

출력 결과 14의 위치에 해당하는 2/4라는 분수값을 얻을 수 있다.

 

 

 

 

 

추가로, 누적합의 역으로 누적값을을 빼면서 찾는 방식도 있다.

X에 layer마다 각 원소갯수를 누적해서 빼주면 X가 layer보다 작아질때가 생기는데 그 때의 layer가 X값이 위치하는 layer이다.

동일하게 짝수층, 홀수층을 나누어 표시한다.

X = int(input())
layer = 1
while X > layer:
    X -= layer
    layer += 1

if layer % 2 == 0:
    top = X
    bottom = layer - X + 1
else:
    top = layer - X + 1
    bottom = X

print(f"{top}/{bottom}")