[백준 17497번] 계산기

난이도: 골드 2

문제 링크: www.acmicpc.net/problem/17497

17497번: 계산기

백준에서는 이 문제를 greedy method라고 분류해는데,

greedy method가 맞는지 개인적으로는 잘 모르겠습니다.

 

처음에는 greedy method 방법으로 접근했습니다.

현재 값 x에서 곱하기, 빼기, 곱하기, 나누기 연산을 해 보고, 주어진 값 N까지의 절댓값이 가장 작은 방법을 고르는 식으로 했는데,

코드도 100줄 가량으로 길어질 뿐더러 N = 3일때 -1이 나오는 등 자꾸 의도치 않은 결과가 나와서...

이 방법은 잘못됐다고 생각했습니다.

 

인터넷 검색을 해 본 후에 제가 새롭게 얻은 아이디어는 두 가지입니다.

1. 0에서 N을 만드는 과정이 아닌, N에서부터 시작해서 0을 만들어 보자.

2. bitmask operator를 이용해 보자.

 

1번의 경우, 이진수적 관점에서 접근한다면,

특정 자릿수의 비트가 활성화되는 것을 목표로 접근하는 것보다,

모든 자릿수의 비트가 비활성화, 즉 0이 되는 것을 목표로 하는 것이 구현상 더 쉽습니다.

 

2번의 경우,

가장 주목할 것은 N의 0번째, 1번째 비트입니다.

 

0번째 비트가 1이면, N은 홀수라는 의미가 됩니다.

이 때는, 더하기 및 빼기로는 이를 바꿀 수 없으므로, (2를 더하거나 빼는 것은 1번째 자리 비트에 관여하므로)

곱하기 계산을 통해 0번째 자리 비트를 0으로 바꿔 줍니다.

 

0번째 비트가 0이고, 1번째 비트가 1인 경우,

뺄셈 연산을 통해 1번째 비트를 0으로 바꿔 줍니다.

덧셈 연산을 해도 1번째 비트를 0으로 바꿀 수는 있지만, 그럴 경우 2번째와 그 이상 비트의 값이 변할 수 있으므로 비효율적입니다.

 

0번째, 1번째 비트가 모두 0일 경우,

나누기 연산을 통해 비트를 당겨 옵니다.

예를 들자면,

N = ...10010001001100 일 경우, 2로 나누면 (이진수로는 10),

N = .........100100010011 가 됩니다.

 

위 세 과정을 계속 반복하다 보면,

모든 비트가 0이 될 때까지 진행하게 되고,

0이 되었을 때 문제에서 요구하는 출력을 진행하면 됩니다.

 

참고한 글은 아래와 같습니다 (코드는 보지 않았음):

• sejinik.tistory.com/145

*코딩 테스트 스터디 그룹을 통해 접한 문제입니다. 링크

CodeTest-StudyGroup/Code-Test-Study