문제 링크
문제
티어: 골드 2
알고리즘: 비트마스킹, 그리디
입력
첫 번째 줄에 정수 N (1 ≤ N ≤ 1013) 이 주어집니다.
출력
첫 번째 줄에 버튼을 누른 횟수 K (0 ≤ K ≤ 99) 를 출력합니다. 누른 횟수를 최소화 하지 않아도 됩니다. 단, 누른 횟수가 99번을 넘으면 안됩니다.
만약 99번 안에 N을 만드는 방법이 존재하지 않는다면 첫 번째 줄에 "-1" 하나만 출력하고 더 이상 아무것도 출력하지 않아야 합니다.
두 번째 줄에는 버튼들을 누른 순서대로 공백을 사이에 두고 출력합니다. 버튼은 "[+]", "[-]", "[*]", "[/]" 중 하나이어야 합니다. 각 버튼의 기능은 지문에 서술되어 있습니다.
방법이 여러 가지인 경우 그 중 하나만 출력합니다.
풀이
초기에 X가 0일 때, 정수 N이 주어지면, 버튼을 잘 눌러 X가 N이 되도록 해야 한다.
문제에서는 누른 횟수를 최소화 하지 않아도 된다고 했지만, 최소화하는 방향으로 가야 N이 될 수 있는지 없는지를 체크할 수 있다. 왜냐하면 누른 횟수는 최대 99번이기 때문이다.
최소화하는 방향은 당연히 곱셈 연산을 위주로 나머지 연산은 최소로하는 것이다.
그런데 잘못된 방식으로 구현을 하다 많은 시간을 낭비했고, 결국 힌트를 봤다.
그 힌트는 비트마스킹이다.
0번째 비트가 1인 경우는 무조건 홀수다.
홀수인 경우에는 /2가 딱 떨어지지 않는다. (N -> 0으로 만들거기 때문에 N에서 /2 연산은 0 -> N에서는 *2 연산임 그렇기 때문에 딱 떨어져야 됨 또한 비트 연사으로 봤을 때 /2하면 1이 버려지기 때문에 정확한 값이 아님)
/2를 하기 위해서는 홀수를 짝수로 바꿔줘야 하는데 이 상황이 곱셉을 위해서 나머지 연산이 꼭 필요한 상황이 된다.
그래서 0번째 비트를 0으로 바꾸는 *2가 필요하다.
그리고 1번째 비트가 1인 경우는 -2를 통해서 0으로 바꿀 수 있다.
이를 이용해서 앞에 있는 비트를 1번째 비트까지 /2로 땡겨오고, 이를 -2하면 답을 구할 수 있다.
위 풀이는 앞에서 말했던 곱셈 연산을 위주로 나머지 연산을 최소로 하기 때문에 99번만에 값을 만들지 못하면 -1를 출력해도 정답이 된다.
소스 코드
import java.io.*;
import java.util.*;
public class Main {
static long N;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Long.parseLong(br.readLine());
Stack<String> stack = new Stack();
int cout = 0;
while(N != 0) {
if(N == 2) {
N -= 2;
stack.push("[+]");
} else if((N & 2) == 2) {
//첫 번째 비트가 1인 경우
N -= 2;
stack.push("[+]");
} else if((N & 1) == 1) {
//0 번째 비트가 1인 경우
N *= 2;
stack.push("[/]");
} else {
//0, 1번째 비트가 0인 경우는 앞에서 1를 끌어온다.
N /= 2;
stack.push("[*]");
}
cout += 1;
if(cout > 99) {
cout = -1;
break;
}
}
System.out.println(cout);
if(cout != -1) {
StringBuilder sb = new StringBuilder();
while(!stack.isEmpty()) {
sb.append(stack.pop()).append(" ");
}
System.out.println(sb.toString().trim());
}
}
}