백준 C++ 9506번 약수들의 합 ( 제곱근, 완전수 )

 

이래저래 기분이 안 좋은 날.

월요일인데..

일진이 안좋다.

새벽 5시에 자서 오후 2시에 일어난 거부터가 기분이 안 좋았다.

 

---

 

문제는 완전수를 구하는 거였다.

분명 나는 푼 적이 있는 거 같은데 말이다.. 흠흠..

분명 그 공식 같은 게 있었는데... 2로 나누고.. 어.. 음음

ㅋㅋㅋㅋ

 

차근차근해보자.

먼저 약수를 구하는 법을 알아보자.

 

제씨는 나에게 간단? 한 방법을 알려주었다.

그냥 숫자를 싹 돌려서

나눠지면 벡터 안에 넣고,

총합으로 더해준다음에

그 값이 같으면 출력

아니면 NOT 어쩌고 해 주면 된다.

 

 

.. 어.. 방법은 괜찮은데

뭔가? 비효율적일지도 모른다는 생각이 들었다.

 

아! 그리고 -1이 나오면 종료라고 해서 나는 

while문을 사용했다.

 

그리고 이렇게

 

출력식을 써주면 끝!

 

위에서 비효율적이라고 했는데

그게 계속 마음에 걸려서

최적의 풀이법? 에 대해 물었다.

 

짝꿍 약수에 대해 알려주었다.

 

약수는 12로 예시를 들면

1 12

2 6

3 4

이렇게 되어있을 때

1을 약수로 찾으면 12는 자동약수가 되며

2를 찾으면 6이 자동으로 약수가 된다.

3을 찾으면 4도 자동으로 된다.

 

그렇기 때문에 짝꿍약수로, 이걸 같이 구하면 계산 횟수가 반토막 난다는 뜻이다.

 

그렇기 때문에 12의 반만 for문으로 돌려도 된다는 말씀!

12의 반은 6인데

3 다음에 4차례인데

4는 이미 3이랑 짝꿍이고

5는 없고

6은 이미 2랑 짝꿍이니..

해줄 필요 없다.!

 

반만 해주면 된다.

 

아 근데 제씨 자꾸 나한테 도발? 한다.

또 이문제를 알려주며 더 효율적인 식이 있다고 나를 홀린다.

 

또 그럼 물어보게 된다.

 

ㅋㅋㅋㅋ

제곱근 방식에 대해 알려주었다.

sqrt라고 부른다는데..

 

fo문에서 i*i <= n을 해준다.

반환점이라고 하는데

예를 들면 

36에서 약수를 구하면

1 36

2 18

3 12

4 9

6 6 < 이 기점인데

여기서는 9여도 4

그 위에 12여도 3이기 때문에

제곱근까지만! 조건을 돌리는 것이다.

 

그래서 제곱근까지만 돌리고

if ( i!= n) 이건

아까 덧셈에서 자기 자신은 빼라고 해서 조건을 걸어둔 것이다.

 

그리고 이것만 해주면 반만 해주는 거라

1,2,3 만해주는 거라 짝꿍도 해주어야 한다.

 

짝꿍은 * i 했을 때 n 이여야 하니까

짝꿍 = n / i;

그리고 위에 조건이 두 개나 필요하다.

1. 자기 자신 제외

2. 아까 36처럼 6 * 6 인애는 6이 한 번만 들어가야 하기 때문에

짝꿍!= i 가 되어야 한다.

안 그러면 두 번 들어간다..

 

이렇게 해주면

1 2 28 3 12 이렇게 저장이 되기 때문에

sort 해줘야 한다.

 

해주고 밑은 그대로 해주면 된다.

 

식을 더 짧게 줄이는 법은

cout << v [i] << ( i == v.size()-1? " " : " + ");

이렇게 해 줄 수 있다고 한다.

나도 삼항연산자 좀 잘 써보고 싶다.

 

 

---

 

오늘 문제를 풀면서..

실력이 늘었나..? 하며 전의 문제를 풀수있을까 생각했을때..

아닐거같다는 생각이 들었다.

 

새로운 문제 1 기존 문제 1 이렇게 해볼 수 있을까..? ㅎㅋ

음...

일단 지금 생각은 그렇다.

이게  는다는 느낌이 없어서 그런지 불안하긴 하다.

 

그래도 하루 고생했다..

내일은 푹 자고 좋은 컨디션으로 풀어야겠다..ㅎ!