[자바] 백준 1402 - 아무래도이문제는A번난이도인것같다 (java)

 문제 : boj1402

---

 

필요 알고리즘 개념

• 애드 혹(AD HOC)
  
  • 정형화된 방식이 존재하지 않고 이 문제만의 아이디어를 생각해내야 한다. 이하 애드혹에 대한 위키 내용이다.
  • "이것을 위해" 즉 "특별한 목적을 위해서"라는 뜻의 라틴어로, 일반적으로 다음을 나타낸다.
    1. 특정한 문제나 일을 위해 만들어진 관습적인 해결책
    2. 일반화할 수 없는 해결책
    3. 어떤 다른 목적에 적응시킬 수 없는 해결책

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  이 문제는 이하에서 명시된 수학과 컴퓨터과학, 언어학 또는 엮인 분야에서 어떠한 문제를 해결하기 위해 정해진 일련의 절차에 해당하는 문제입니다.

"이것을 위해" 즉 "특별한 목적을 위해서"라는 뜻의 라틴어로, 일반적으로 다음을 나타낸다.
1. 특정한 문제나 일을 위해 만들어진 관습적인 해결책
2. 일반화할 수 없는 해결책
3. 어떤 다른 목적에 적응시킬 수 없는 해결책

 

.. 한글날이라 영어 없게(알고리즘, 애드혹) 쓰려다보니 뇌절해봤습니다.

 

 

  소인수분해도 해주고, 범위가 2^31이니깐 소수(prime number)는 따로 찾아서 계산해줘야 시간초과 안나게 생긴 문제이다. 처음엔 이렇게 생각했는데, 내가 이 문제에서 힌트를 얻은 부분은, A와 B가 음수도 가능했다는 점이다. 약수의 경우 'Divisors can be negative as well as positive, although sometimes the term is restricted to positive divisors. For example, there are six divisors of 4; they are 1, 2, 4, −1, −2, and −4, but only the positive ones (1, 2, and 4) would usually be mentioned.'으로 일반적으로 약수라고 하면 양의 정수로 생각하지만, 음의 정수도 당연히 약수로 가능하다. 보통 양수만 쓸 뿐이다. 하지만 어찌됬든, 알고리즘 문제에서 음수 약수를 요구하는 경우는 거의 없다(1400문제정도 풀었지만 음수인 약수를 구하는 경우는 한번도 없었음.). 그래서 다른 방식으로 생각해봤고, 결과적으로 A와 B를 볼 필요도 없이 모두 yes를 출력해주면 된다.

 

  이하의 2가지에 따라 모두 yes가 된다.

1. A == A*1

2. A == A*(-1)*(-1)

 

  즉 어떠한 음수도 만들 수 있고(-1이 2번 들어가야되서 음수는 2씩 차이나야 되지 않냐고 할 수 있는데, 거기에 또 '1'을 적용시켜주면 된다.), 어떠한 양수도 만들 수 있다. 예를들어 예제 입력 1의 경우 A=6, B=5에서, A = A*(-1)*(-1)*1 이므로, A-1-1+1 = B 이다.

 

  코드에서 StringBuilder에 y,e,s를 각각 따로 append해준 이유는 저게 약간 더 빠르다 ㅋㅋ. 어차피 시간 충분만 문제라서 append("yes\n") 해줘도 동일하다.

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (t-->0) {
            sb.append('y').append('e').append('s').append('\n');
        }
        System.out.print(sb);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}