-
[java] 백준 알고리즘 1011번 Fly me to the Alpha Centauri 풀이알고리즘/백준 알고리즘 2018. 5. 30. 16:13
노가다겠지만,
거리가 1~25까지 최소 작동 회수를 구해보면 좋을 듯 싶다.
종이에 옮겨놓으면 그나마 이해가 될 때가 많다.
0~1, 0~2, 0~3, 0~4 쭉쭉 최소 작동 회수를 구해본다.
0에서 해도 되는 이유는 결국 거리를 얼만큼 최소로 이동하느냐기 때문에
45~50이 입력되든 0~5가 입력되든 거리는 5라서 상관이 없다.
쭉쭉 구하다보면 완벽한 데칼코마니가 되는 순간 이후부터 최소 작동회수가 올라간다.
예시)
0에서 1(총 1번): 1
0에서 2(총 2번): 11
0에서 3(총 3번): 111
0에서 4(총 3번): 121
0에서 5(총 4번): 1211
0에서 6(총 4번): 1221
0에서 7(총 5번): 12211
.
.
.
.(중략)
.
0에서 12(총 6번): 123321
0에서 13(총 7번): 1233211
.
.
.
0에서 20(총 8번): 12344321
0에서 21(총 9번): 123443211
서서히 빨라졌다 서서히 느려지는게 최소횟수가 되는 것이다.
그 외에는 대충 끼워넣기 느낌 밖에 들지 않는다
데칼코마니를 찾기 위해
앞에서 부터 그리고 뒤에서 부터 숫자를 더해주고 빼준다.
그와 동시에 작동한 횟수를 ++ 해준다
완벽한 데칼코마니 혹은 x쪽에서 데칼코마니를 넘었을 땐 break
x가 움직인 후 y쪽에서 완벽한 데칼코마니를 넘었을 땐 거기서 break
* 풀이 소스
123456789101112131415161718192021222324252627282930313233343536373839404142public class Baekjoon1011 {static StringTokenizer st;public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));st = new StringTokenizer(br.readLine());int t = Integer.parseInt(st.nextToken());for(int i=0; i<t; i++) {st = new StringTokenizer(br.readLine());int x = Integer.parseInt(st.nextToken());int y = Integer.parseInt(st.nextToken());int movingDistance = 0;int xMovingCount = 0;int yMovingCount = 0;while(true) {movingDistance++;x += movingDistance;xMovingCount++; // x의 이동횟수if(x >= y) {break;}y -= movingDistance;yMovingCount++; // y의if(y <= x) {break;}}bw.write(String.valueOf(xMovingCount+yMovingCount));bw.newLine();}bw.flush();}}cs '알고리즘 > 백준 알고리즘' 카테고리의 다른 글
[java] 백준 알고리즘 1475번 방 번호 풀이 (0) 2018.05.31 [java] 백준 알고리즘 2775번 부녀회장이 될테야 풀이 (0) 2018.05.31 [java] 백준 알고리즘 1193번 분수찾기 풀이 (0) 2018.05.30 [java] 백준 알고리즘 10250번 ACM호텔 풀이 (0) 2018.05.29 [java] 백준 알고리즘 15802번 타노스 풀이 (0) 2018.05.28