백준 C++ 1193번 분수찾기 ( break, continue )

 

분수.. 찾기?

이름은 쉬울 줄 알았는데

문제는 진짜 기가 막히게 어렵다

이걸 무슨 수로 푼담? 이거 브 2문제 아니었나요?!

 

패턴도 못 찾을 거같이 생긴 이 문제

같이 풀어봅시다 ㅎㅋ

 

아! 나는 요즘 신비님이 부르신 사랑스러워를 듣고 있다.

나 어릴 땐 김종국의 사랑스러워를 알람소리로 했는데 말이다.

노래가 좋아서 자주 듣고 다녔는데

우연히 신비님의 노래로 들어보니

진짜 산뜻해지는 느낌이 들어서 요즘 문제 풀면서 듣고 있다.

 

좋다.

이 리메이크 곡은 "아름다웠던 우리에게"라는 드라마 ost곡인데

 

나는 이 드라마의 원작을 너무너무너무 좋아한다.

시간이 남는다면 또 보고 싶다.

다시 봐도 재밌는데 말이다.

 

드라마 원작은 중국의 "치아문단순적소미호"로

너무너무 유명한 중드이다.

이 중드의 ost까지 완벽하게 듣고 있으니

나는 이 원작을 좋아하는 게 분명하다.

저기 드라마 맨 끝에 호도 좋아하다 호인데..

호호호!!

 

...

---

 

 

?!? 문제가 이렇게 어려우면 어쩌자는 거죠?

방금까지 치아문 이야기하면서 호호대던 사람 어디 갔죠?!!?

 

규칙이 뭘까..?

...

전혀 모르겠다.

지 선생에게 도움을 요청한다.

문제를 본 지 10분 만에 요청한다. 왜냐면...

진짜 모르겠기 때문이다.

아마 근래 풀었던 것 중 가장 생각조차 안 들게 하는 문제가 아닐까..?

 

힌트를 여러 개 줬다.

1... 짝수... 는 짝수개고..

홀수는.. 홀수개라는 것...

그렇지.. 그렇지...

 

2..... 1+2+3+4.. 이렇게 크기가 계속 커진... 다...

그렇지... 그니까.. 10은 4.. 안에 있겠지...

 

....

---

 

지피티의 조언은 이랬다.

 

맞아요.. 그렇죠 n번째 대각선.. 에 n개의 분수가 있다.

 

오케이 

아니 여기까지는 알겠는데..

 

 

이게 뭐요?

하며 다시 패턴을 보니... 지그재그가.. 이런 지그재그였다.

 

아.... 이제 이해가 좀 간다.

짝수일 땐, 분모가 작아지고

홀수일 땐, 분모가 커진다.

 

그 뜻이었다.

---

 

 

자 정리하면,

숫자를 보고

몇 번째 대각선에 들어갈지 보고..

그 줄의 대각선을 확인하고 대각선이 짝수인지 홀수인지 파악해서...

분모 분자를... 구하면 되...나?

 

.. 어려운데?!

 

 

line은 대각선의 개수 처음에 1로 시작할 땐 1개니까 1로 시작.

cnt 또한 1개에는 분수가 1/1 하나니까 1

 

line으로 대각선이 몇 번째인지 기억하고

cnt로 대각선에 분수가 몇 개인지 기억한다.

 

 

n을 cnt 빼준다.

그리고 cnt랑 line을 1씩 더한다

사실 몇 번째 대각선에 따라 분수의 개수가 같기에 같이 더해준다.

그렇게 n이 cnt보다 작아지면

n의 숫자에 따라서 몇 번째에 있는지만 알면 된다.

 

 

num 은 분자

den 은 분모

 

짝수의 경우

4라고 치면

분모는 4 > 3 > 2 > 1

분자는 1 > 2 > 3 > 4

 

분모는 작아지고 분자는 커진다.

 

여기서 n은 cnt로 계속 빼줬으니

8번째면..

8 - 1 = 7

7 - 2 = 5
5 - 3 = 2

그럼 2일 텐데..

반대로 생각하면

2가 남았다는 건 4번째 대각선에서 2번째라는 거기 때문에

그 n을 활용해서

 

분자는 n;

분모는 4 - n +1을 해준다.

8로 치면 지금 2/3 이 나오게 된다.

 

 

반대도 마찬가지!

 

홀수의 경우

5라고 치면..

분자는 1 > 2 > 3 > 4 > 5
분모는 5 > 4 > 3 > 2 > 1

 

분모는 커지고 분자는 작아진다.

 

5의 경우 

5 - 1 = 4

4 - 2 = 2

3에 2니까..

num = 2

den = 2

 가 나오게 된다.

 

?!? 왜 분모에 line - n +1을 해줄까?!

 

그 이유는

분자와 분모를 더하면 알 수 있다. 1/5 면 6

2/4 해도 6 3/3 해도 6

 

분모와 분자를 더하는 건 분모 +1인 사실

이걸 적용하게 되면

 

5에서 아까

분자인 num으로 2일 경우

분모를 찾으려면

전체에서 분자를 빼면 된다.

아까 전체 ( 분모 + 분자 )가 분모 +1 이기 때문에

line +1 - num이 되는 것이다!!!

 

---

 

더 간단하게 풀 수 있긴하다.

그냥 입력값과 몇번째줄인지만 알면 바로 계산이 된다.

 

1부터 시작이고 몇번째줄인지 알려면 

x -= line 해주면 되고

line++ 해줘서 누적해준다음에 빼주면

x > line 일때만 굴려주면 된다.

 

이렇게 굴려주면

이게 line줄에 x번째기 때문에

x이 분자 또는 분모가 되게 된다.!

 

분자 +  분모 = 분모 +1 이니까

아까 밑 식 처럼

 

 

해주면 끝!!

 

---

 

wow!

 

 너무 어렵다.

 

이걸... 다 이해하기 까지.. 꽤 오래 걸렸다.......

 

내가 다음에도 풀 수 있을까??..... 고통스럽군..

 

... 몰라 내일도 와서 풀어봐야지