유튜브 ALGORITHM JOBS 채널에서 풀이해준 영상을 통해 배우고 공부한 내용 정리
https://www.youtube.com/watch?v=WHUiwMki0aY
문제 : 숫자 n을 3의 거듭제곱 숫자들을 중복 없이 더해서 만들 수 있는지 구하여라.(1도 3^0의 거듭제곱으로 본다.)
제한시간 : 5분
이 문제의 포인트는 "중복 없이 더해서 만들 수 있는지" 라는 문구이다.
예시는 다음과 같다.
109는 3^0+3^3+3^4로 나타낼 수 있다.
7은 3^0+3^1+3^1로 나타낼 수 있지만 3^1을 두 번 사용(중복)했으므로 이식은 사용할 수 없다.
예시를 통해 7은 3의 거듭제곱 숫자들을 중복 없이 더해서 만들 수 없는 것을 알 수 있다. 즉 중복이 필요한지 아닌지를 확인 하기 위해서는 주어진 숫자를 3진수로 나타내 봐야 한다.
3진수로 표현했을 때 2가 있으면 불가능하고 없으면 가능하다.
3진수를 구하는 방법은 몫이 0이 나올 때까지 쭉 나누기 연산을 했을 때 연산과정에서 발생하는 나머지 값을 역순으로 나열하면 된다.
문제를 빨리 풀어야 하므로 연산 과정 중 나머지가 2가 나오면 바로 그 숫자는 3의 거듭제곱 숫자들을 중복 없이 더해서 만들 수 없는 숫자이기 때문에 바로 다음 문제로 넘어가는 것이 좋지 않을 까 생각한다.
1번) 36
2번) 120
3번) 278
4번) 19424
5번) 10492831
해당 영상에서 소개한 문제에 대한 5가지 문제에 대한 필자의 풀이는 다음과 같다.
5번과 같이 숫자가 커지면 이렇게 다 손으로 계산하는 것은 비효율적이다.
따라서 공학용계산기를 이용하는 것이 좋을 것이다.
(실제 정답과 다를 수 있고, 풀이과정에 오류가 있을 수 있습니다.)
