1193 분수찾기

으아악 너무 힘들었다. 규칙 찾는 문제인 것 같은데 이걸 어떻게 하지 하다 고등학교 때 이런 문제 푼 것 같아서 그냥 그 기억 그대로 풀었다. 보면 1/1 ~ 2/1 ~ 3/1 이런 덩어리로 볼 수 있으니 그 덩어리 안에서 몇 번째인지 구하면 X가 나온다. 

 

그런데 저렇게 코딩하면 이상하게 나온다? 알고보니 내가 문제를 잘 못 읽었다. 순서를 잘못 붙여서 결과가 다르게 나온다.. 허어..어.. 

다행이도 조금만 고치면 해결되는 문제였다. 

#include <iostream>

int main() {
    int x;
    scanf("%d", &x);
    
    for(int i = 1; ; i++){
        int num = 1 + i*(i-1)/2;
        if(x < num){
            int index = i - 1;
            int sub = x - num + i - 1;
            
            if((i-1)%2 == 1)
                printf("%d/%d", index-sub, 1+sub);
            else
                printf("%d/%d", 1+sub, index-sub);
            break;
        }
    }
    return 0;
}

맞췄음..

 

돌리기 전 걱정되는 부분은 시간제한이 0.5초인거! O(n)일때 대략 1억번을 돌 수 있으니 0.5초면 그 반.. 5천번 돌 수 있을 것이다 (맞나여) 다행히 입력이 1천이라 괜찮을 것 같았다. 게다가 코드를 보면 알겠지만 for문이 한 개이긴 하지만 n만큼은 안 돔.. 

 

두 번째는 int num = 1 + i*(i-1)/2; 여기서 num 터지지 않을까 싶은거. 사실 이거 다 짜고 힘들어서 그냥 돌려서 맞길래 넘어갔는데, 음.. 엄.. 모르겠다. 왜 안 터졌지. 저렴한 생각으로 치면 x < num이므로 num은 x와 비슷한 값일 것이다. 10^7 + (얼마) 겠지.. 근데 그 얼마 더해봤자 10^9까지 안 갈 것 같아서 안 터진 거 같다. 

 

 

---

오.. 몰랐던 거..

 

n은 i의 제곱에 비례해서 실제로 시간복잡도는 루트가 된다. 그래서 입력이 1억의 제곱은 1조 정도까지 범위로 들어와도 1초 안에 수행 가능하다!