BAEKJOON : 1193, 2869

No. 1193

1. Problem

2. My Solution

• 입력 n 까지 분수를 모두 구하는 방식 -> 시간초과

import sys

n = int(sys.stdin.readline().strip())
count = 1
top = 1
bottom = 1
level = 2
flag = True     
loopflag = True
while(True):

    if loopflag == True and n == count:
        print(f"{top}/{bottom}")
        break

    for i in range(1,level+1):
        
        if count == n: 
            loopflag = True
            break
        
        elif flag == True and i == 1:
            bottom += 1
            count += 1

        elif flag == True:
            bottom -= 1
            top += 1
            count += 1

    
        elif flag == False and i == 1:
            top += 1
            count += 1  

        elif flag == False:
            top -= 1
            bottom += 1
            count += 1

    level += 1
    flag = not flag 

3. Others' Solutions

• 사선라인에서 가장 큰 값은 1 + 2 + 3 ... n(사선라인 레벨)
• 사선라인이 몇 번째인지 나타내는 수의 짝수 / 홀수 여부로 알고리즘 구현

import sys

n = int(sys.stdin.readline().strip())

level = 1
level_max = 1

while(n > level_max):
    level += 1
    level_max += level

pos = level_max - n 

if level % 2 == 0:  
    top = level - pos 
    bottom = pos + 1
    
else:
    top = pos + 1
    bottom = level - pos

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

4. Learned

• 모든 규칙을 찾아보고 어떤 규칙을 이용해서 알고리즘을 구현할지 생각하자

---

No. 2869

1. Problem

2. Others' Solutions

• 달팽이는 하루에 a - b만큼 이동한다
• 하지만 목표지점에 도달 했을 때는 미끄러지지 않으므로 하루에 최대 v - b만큼 올라갈 수 있다
• (a*n) - (b*n) + b >= v 에서 n(일수)을 기준으로 이항
• n >= (v-b)/(a-b) 에서 n(일수)는 자연수 이므로 나머지가 0이 아니면 +1을 한다

import sys

a,b,v = map(int,sys.stdin.readline().strip().split())

if (v-b)%(a-b) == 0:
    print((v-b)//(a-b))
else:
    print((v-b)//(a-b)+1)

3. Learned

• 식에 입력을 하나씩 넣어서 값을 찾아야되는 알고리즘에서 시간초과가 발생한다면 해당 식의 입력값을 기준으로 이항해서 풀자
• 식에서 해당 요소의 단위를 생각하자 (자연수인지 실수인지)