[백준] 1193번 분수찾기

 

[아이디어]

규칙 찾는것도 힘들었는데 시간 초과..도저히 내머리로 빠른 방법을 떠올릴수없어서 다른 풀이를 참고해 풀었다.

어케 풀이를 저렇게 생각해낼수있는지 그저 대단하다

 

위 배열을 대각선을 기준으로 나눠서 보자. 

 

1번째 대각선 - 1/1
2번째 대각선 - 1/2, 2/1
3번째 대각선 - 3/1, 2/2, 1/3
4번째 대각선 - 1/4, 2/3, 3/2, 4/1
5번째 대각선 - 5/1, 4/2, 3/3, 2/4, 1/5

.

.

여기서 발견할 수 있는 규칙

• i번째 대각선에는 i개의 원소가 존재한다.
• i번째 대각선에는 i까지 분자가 증가한다.
• 짝수번째 대각선에서는 분모가 감소, 분자가 증가한다.
• 홀수번째 대각선에서는 분자가 감소, 분모가 증가한다. 

이 규칙을 가지고 구현하기 위해서 입력받은 숫자 N이 몇번째 대각선의 몇번째 원소인지 알아야 한다.

이건 i가 1씩 커지면서 N에서 i만큼 빼주면 찾을 수 있다. (첫번째 규칙에 의해)

반복문을 다 돌고나면 이제 N은 i번째 대각선의 N번째 원소를 뜻하게 된다.

 

 

[Wrong] - 시간 초과

import sys
input =sys.stdin.readline

n=int(input().rstrip())
x,y=1,1
cnt=1

while cnt<n:
    if x==1: #행=1되면 열+1
        y+=1
        cnt+=1
        #내려갈 차례, 행+1,열-1
        while cnt<n:
            if y==1: #열=1 되면 탈출
                break
            x+=1
            y-=1
            cnt+=1
    if cnt==n:
        break
    if y==1: #열=1되면 행+1
        x+=1
        cnt+=1
        #올라갈 차례, 행-1,열+1
        while cnt<n:
            if x==1:
                break
            x-=1
            y+=1
            cnt+=1
print("%d/%d"%(x,y))

 

[해결]

import sys
input =sys.stdin.readline

n=int(input().rstrip())
x,y=1,1
i=0

while n>i:         #n이 몇번째 대각선에 위치하는지 알아보자.
    n-=i
    i+=1
                   #이제 N은 i번째 대각선의 n번째 원소임을 나타냄.

if i%2==0:         #짝수번째 대각선에 있다면, 분모 감소, 분자 증가
    x=n
    y=i-n+1
else:              #홀수번째 대각선에 있다면, 분모 증가, 분자 감소
    x=i-n+1
    y=n
print("%d/%d"%(x,y))

 

 

참고

https://codesyun.tistory.com/entry/BOJ%EB%B0%B1%EC%A4%80-1193%EB%B2%88-%EB%B6%84%EC%88%98%EC%B0%BE%EA%B8%B0-C-%EB%AC%B8%EC%A0%9C-%ED%92%80%EC%9D%B4

[BOJ/백준] 1193번 분수찾기 C++ 문제 풀이