백준 C++ 2231번 분해합 ( 브루트포스 )

정말 오랜만입니다.

이래저래 바빠서 문제를 풀 새가 없었습니다.

긁적

굉장히 그.. 네 죄송..(?) 합니다.

하지만 깃허브의 잔디는 잘 채웠습니다.

플젝 리드미를 수정했기 때문이지요.

 

하던 프로젝트 사람들이 다 떠나고 저만 남아버려서..

리드미를 전체적으로 수정하는데 종일 걸렸네요....ㅎㅎㅋ

 

사실 완벽하게 다한건 아니지만..!

그래도 어느 정도 정리는 했습니다.

여하튼 제 깃허브 잔디는 아직 유효합니다.

 

뿌듯.. q(≧▽≦q)

ㅋㅋㅋㅋ

 

오늘의 문제를 볼까요?!

---

 

시작은 호기롭게 했으나...

하나도 모르겠고

읽어도 모르겠고

..

..

15분 뒤 뭐 이해를 한 건가 싶었다.

결국 문제는 큰 수를 보고 작은 수를 맞추는 건데

.. 이게 되나?? 말이 안 되는데..

 

괴로워하며

내 친구 인공지능씨에게 갔다.

 

인지 씨는 나에게

자연수가 백만까지니까 그냥 1부터 N까지 일일이 해보라고 했다.

컴퓨터는 백만정도면 그렇게 힘들어하지 않는다면서 말이다.

 

말 따라 해 봤다.

숫자와 그 숫자의 각 자릿수를 더하고

그 숫자가 N과 같으면 된다.

 

잘 썼다

하지만 테스트는 엉망이다.

 

 

뭐가 문제인지 몰라

한풀이와 함께... 문제점을 알려달라고 했다.

 

 

.. 고맙소...

난 지금 배신당한 거겠지...?

 

두 가지의 원인은 이랬다.

1. i를 수정하면 결국 i는 0인데..

그럼 i++하면 1이고 for문이 무한반복되는 문제 발생

 

즉! i를 만지면 안 된다.

복사본이 필요!!

 

그래서 tmp를 만들었습니다!!

 

2. 출력을 sum으로 하면 n을 출력하는 건데

우리는 i를 출력해줘야 한다.

i가 곧 생성자가 될 거니까.!

 

수정..!

 

아니 문제 이해했다면서 2번도 못해?!!?

으휴흐으으

---

 

 

가장 효율적인 풀이법을 인지 씨가 공유해 주었다.

탐색범위를 좁히는 원리

 

ㅇㅅㅇ?

N = M + (M의 각 자릿수의 합)

으로 이루어져 있다.

 

N은 1,000,000 까지라니까

M의 최댓값을 생각해 보면 각 자릿수까지 더할 거니까

아마.. 999,999.. 보다 아주 조금 작을 테니

즉 6 자릿수인 건 변하지 않는다!

6자리 수일테니 한 자릿수에서 최댓값이 9니까

 

M + M의 각 자릿수는

M + ( 9 * 6 = 54 )

54보다 커지진 않는다는 것!

 

그것을 활용하여 다시 풀었다.

 

 

인지 씨는 칭찬해 줬다.

그리고 문제점........ 두 가지를 또 알려주었다.

 

1. 생성자가 없는 경우에 0 출력해줘야 한다. 잊지 말고 for문 뒤에 cout << 0 해줘라

 

2. 만약에 num이 음수면 어떡할 거냐?
n이 5라면 cnt는 1이 되고 5-9 라 -4가 된다.

음수를 % 10으로 나누는 것은 숫자가 이상해진다!!

 

그래서 음수가 아니게끔 제약을 걸어줘야 한다!

if(n <0) num = 0;

음수면 0부터 시작하시오!!!

 

이렇게 해주면 답이 나온다고 한다.

 

왘!!!!

 

사실 인지 씨의 답은

그냥 어차피 최댓값이 54고 우리가 알고 있는 정보니까..

그냥 n에서 -54를 해주고!

만약에 음수일 때만 제약을 걸고 그대로 하면 된다고 하셨다.

 

그것도 그렇다.

 

더 단순한 방법도 있다는 것을 알았다.

 

이렇게 풀어보니 참 쉽다..

분명 어려워서

한 발자국도 못 나갈 거 같았는데.

그래도 또 한 발자국 나갔다.

 

두 발자국을 위해

오늘은 20000 쉰다 히히

 

해산!