백준 기본수학 1 풀이 - 2

백준 단계별로 풀어보기 - 기본수학1 문제 2개 python으로 풀기

---

1193 - 분수 찾기

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

이와 같이 나열된 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자. X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.

x = int(input())
exp = 1; i = 1; n = 1
while (1):
  if (i <= x) and (x < (i + exp)):
    if n % 2 == 0: print(str(1+x-i)+'/'+str(de-(x-i)))
    else: print(str(de-(x-i))+'/'+str(1+x-i))
    break
  else: 
    n += 1; i += exp; exp += 1

풀이 : 분수들은 1/1 || 1/2 2/1 || 3/1 2/2 1/3 || 1/4 2/3 3/2 4/1 || ... 순으로 전개가 된다. || 을 기준으로 나누었을 때 n번째 구간에는 양 끝에 n이 들어간 분수가 존재한다. 또한 n이 홀수일 때는 분자가 줄어들고 분모가 커지고 n이 짝수일 때는 분자가 늘어나고 분모가 줄어든다. x가 주어졌을 때 n이 무엇인지만 알 수 있다면 원하는 결과를 얻을 수 있다. n을 구할 때에는 각 구간에 있는 분수들의 개수를 이용할 것이다. 구간별 첫번째 분수가 전체에서 몇번째인지 적어보면 1, 2, 4, 7, 11, ...이 된다. 그 후에 각 자리수마다의 차이를 구해보면 1, 2, 3, 4, ... 가 된다는 것을 확인할 수 있다. (참고로 각 자리수마다 차이는 각 구간별 분수의 개수와도 같음을 확인할 수 있다) 이 규칙을 이용하여 x가 몇번째 구간에 있는지를 알 수 있다. n을 구하였으면 n이 짝수인지 홀 수 인지를 판별하여 결과를 출력해주면 된다.

---

2869 - 달팽이는 올라가고 싶다

※ 땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다.

달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다. 달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오.

import math
A, B, V = map(int, input().split())
print(int(math.ceil((V-A)/(A-B)))+1)

풀이 : 하루에 A미터를 오른 뒤 밤에 B 미터를 떨어진다. 그리고 정상에 올랐을 때는 더 이상 떨어지지않는다. 해당 문장을 그대로 식으로 써보면 n*(A - B) + A >= V 가 된다. 해당 식을 정리해보면 n >= (V-A) / (A-B) 가 된다. 이 때 n을 그대로 출력하면 안된다. n은 밤이 된다는 것을 포함한 모든 날짜이므로 최종적으로 정상에 다다르는 날을 하루 더 추가하여 출력해주어야 된다. 그리고 정리한 식의 우측항이 분수가 되었을 때에는 올림(math.ceil)을 해주어 계산하여야 한다.