[백준] 1193번 - 분수찾기 (파이썬)

> 

[문제]

무한히 큰 배열에 다음과 같이 분수들이 적혀있다.

이와 같이 나열된 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자.

X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.

 

[설명]

순서를 쭉 써보면 그림과 같이 나온다. 여기서 쭉 보다보면, 몇 개의 규칙을 발견할 수 있다.

설명을 위한 그림

규칙

1. 합이 같은 친구들끼리 그룹으로 묶을 수 있다.

 - 1/2와 2/1은 합이 3이기 때문에 같은 그룹으로 묶을 수 있다. 

 - 그림에는 색깔로 구분을 해두었다.

2. 그 합은 하나씩 증가한다.

 - 노란 그룹은 합이 4였는데, 초록 그룹은 합이 5다. 

3. 그룹에 있는 분수의 개수도 하나씩 증가한다.

 - 초록 그룹은 개수가 4개였는데, 파란 그룹은 개수가 5개다.

4. 각 그룹의 첫번째 분수는 1 또는 합-1의 숫자로 시작한다. (번갈아가며 그렇게 나온다)

 - 2는 1/2 , 4는 3/1, 7은 1/4, 11은 5/1 이다.

5. 그룹 안에서는 내림차순 혹은 오름차순이다. (일정한 순서 有)

 

 

입출력 예시

 

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

1193번: 분수찾기

---

🎨 풀이

💡 전체 코드

X = int(input())
count = 1
total = 2
odd_or_even = False # 1로 시작하는게 True, 아닌게 False 혼자 정한거.

while(True):
    if X-count <= 0:
        break
    else :
        X -= count
        total += 1
        count += 1
        odd_or_even = not odd_or_even

if odd_or_even == True :
    print(str(X)+"/"+str(total-X))
else :
    print(str(total-X)+"/"+str(X))

> 핵심 : 어느 그룹에 속하는 지 찾고, 그 그룹에서 합이랑 순서 이용해서 해당 분수 구하면 된다.

(이해 안되면 위에 규칙 잘 살펴보면 됨)  

           

🍦 코드 설명 (실행 순서대로 나열)

# main

X = int(input())
count = 1
total = 2
odd_or_even = False # 1로 시작하는게 True, 아닌게 False 혼자 정한거.

1. X를 입력받는다.

 - X : 구해야할 분수의 위치 (= X번째 분수)

2. count, total, odd_or_even을 각각 초기화해준다. (1/1 기준)

 - count : 그룹 안에 있는 분수의 개수

 - total : 분자+분모

 - odd_or_even : 1로 시작하는지, 다른 숫자로 시작하는 지 체크해주기 위함.

   - 그 다음이 1/2이기도 하고, 어짜피 1/1이라서 아무거나 해도 상관없기 때문에 복합적인 이유로 False로 적어둠.

 

@ while 무한 반복문 (3번 ~ 8번)

while(True):
    if X-count <= 0:
        break
    else :
        X -= count
        total += 1
        count += 1
        odd_or_even = not odd_or_even

3. while 무한 반복문을 실행한다.

4. 만약 X-count가 0과 같거나, 그것보다 작으면 무한 반복문을 종료한다.

 

5. 아니라면, X - count 를 해준다.

6. total에 1을 더해준다.

 - 그룹이 늘어나면 합도 1 증가하기 때문임.

7. count에도 1을 더해준다.

8. odd_or_even을 바꿔준다.

 - not 을 앞에 붙이면 True -> False  /  False -> True로 바뀜.

 

# main

if odd_or_even == True :
    print(str(X)+"/"+str(total-X))
else :
    print(str(total-X)+"/"+str(X))

9. 만약 odd_or_even이 True라면, str(X) + "/" + str(total-X) 를 출력해준다.

 - True라는 건 해당 그룹의 첫 분수가 1로 시작했다는 뜻이기 때문에 그렇게 해주는 거다. (오름차순임)

10. 아니라면, str(total-X)+"/"+str(X)를 출력해준다.

 - 내림차순으로 진행되기 때문.

---

​끝~

 

⭐ 느낀점

> 그냥 규칙 찾기 문제인데, 뭔가 설명을 잘 한 기분은 아니다. 설명이 어렵네. ㅠㅠ 잘 들여다보고 있으면 규칙이 나온다. 그거 이용해서 풀면 되는 문제다. 나는 이 규칙 찾기 너무 어려워서..? 아니다 그 규칙 찾긴 했는데 긴가민가하기도 했고, 또 중간에 부등호때문에 틀렸는데 다 잘못된 줄 알고 갈아엎기도 했었고 여튼 우여곡절이 좀 많았다. 내 생각에 자신감을 좀 가져야겠다는 생각이 들었다. 그래도 오래 잡고 있던 문제였는데, 풀려서 기분이 좋다. 고생많았다.