[백준]10158번 개미 - Java

문제

https://www.acmicpc.net/problem/10158

10158번: 개미

 

풀이

처음에는 아무 생각 없이 걍 시뮬로 하면 될 것 같았음. 그래서 했는데? 조졌다리

밑에 오답 코드처럼 노가다로 하다가 하면서도 뭔가 이상한 것 같았음 ㅋㅋㅋㅋ 근데 이미 한거 일단 제출해보자 하고 했는데 역시나 메모리 초과(사실 메모리 초과는 문제 풀면서 첨 보는거 같음)

그리고 문제 다시 봤는데 

문제에서 w와 h는 자연수이며 범위는 2 ≤ w,h ≤ 40,000이다. 그리고 개미의 초기 위치 p와 q도 자연수이며 범위는 각각 0 < p < w과 0 < q < h이다. 그리고 계산할 시간 t의 범위는 1 ≤ t ≤ 200,000,000이다. 

범위가 미쳤음,,,, 문제 제대로 읽기의 중요성을 또 한번 깨닫고 다시 풀었음 그래서

 

어떻게 해야할지 모르겠다가 개미가 움직일 시간 t를 늘려가면서 계속 했는데 반복되는 느낌을 받았고, 시간이 1씩 증가할 때마다 개미는 위나 아래로 한칸, 오른쪽이나 왼쪽으로 한칸 무조건 움직인다는 것을 알게 되었음

 

1. 1. 문제의 예제 1번에서 가로만 따졌을 때, 4(t = 0), 5, 6, 5, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5, 6, 5, ... 이렇게 반복이 된다.
2. 2w 씩 반복이 되는 것이다. 따라서 t가 주어지면 2w로 나눈 나머지를 가지고 뭔가를 하면 된다!!!
3. 마지막 답을 구할 때에는 나머지의 값이 w보다 작을 때는 그냥 나머지이고 w보다 크다면 (2w - 나머지)를 해줘야 함

근데 마지막에 출력할 때

System.out.println(c + " " + r);

얘로 하면 틀리고

 

StringBuilder sb = new StringBuilder();
sb.append(c).append(" ").append(r);
System.out.println(sb);

얘로 했더니 맞았다... 이런 일도 처음인 것 같은데.... 암튼 뻘짓을 많이 해서 시간이 오래 걸렸다 ㅠㅠㅜ

 

코드

오답(메모리 초과)

// 오답(메모리 초과)
// 10158번 개미
// https://www.acmicpc.net/problem/10158

package BAEKJOON;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Num10158_개미 {
    // 오른쪽위대각선/왼쪽위대각선/왼쪽아래대각선/오른쪽아래대각선
    static int[] dr = {-1, -1, 1, 1};
    static int[] dc = {1, -1, -1, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int w = Integer.parseInt(st.nextToken());
        int h = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int p = Integer.parseInt(st.nextToken());
        int q = Integer.parseInt(st.nextToken());
        int t = Integer.parseInt(br.readLine());

//        int[][] map = new int[h][w];

        int r = q;
        int c = p;
        int dir = 0;

        int count = 0;

        while (count != t) {

            int nr = r + dr[dir];
            int nc = c + dc[dir];

            // 오른쪽위대각선/왼쪽위대각선/왼쪽아래대각선/오른쪽아래대각선
            if (dir == 0) {
                if (nr < 0 && nc >= w) {
                    dir += 2;
                    nr = r + dr[dir];
                    nc = c + dc[dir];
                } else if (nr < 0) {
                    dir += 3;
                    nr = r + dr[dir];
                    nc = c + dc[dir];
                } else if (nc >= w) {
                    dir += 1;
                    nr = r + dr[dir];
                    nc = c + dc[dir];
                }
            } else if (dir == 1) {
                if (nr < 0 && nc < 0) {
                    dir += 2;
                    nr = r + dr[dir];
                    nc = c + dc[dir];
                } else if (nr < 0) {
                    dir += 1;
                    nr = r + dr[dir];
                    nc = c + dc[dir];
                } else if (nc < 0) {
                    dir -= 1;
                    nr = r + dr[dir];
                    nc = c + dc[dir];
                }
            } else if (dir == 2) {
                if (nr >= h || c < 0) {
                    dir -= 2;
                    nr = r + dr[dir];
                    nc = c + dc[dir];
                } else if (nr >= h) {
                    dir -= 1;
                    nr = r + dr[dir];
                    nc = c + dc[dir];
                } else if (c < 0) {
                    dir += 1;
                    nr = r + dr[dir];
                    nc = c + dc[dir];
                }
            } else if (dir == 3) {
                if (nr >= h || nc >= w) {
                    dir -= 2;
                    nr = r + dr[dir];
                    nc = c + dc[dir];
                } else if (nr >= h) {
                    dir -= 3;
                    nr = r + dr[dir];
                    nc = c + dc[dir];
                } else if (nc >= w) {
                    dir -= 1;
                    nr = r + dr[dir];
                    nc = c + dc[dir];
                }
            }
            r = nr;
            c = nc;
            count++;
        }
        System.out.println(c + " " + r);
    }
}

 

정답

// 10158번 개미
// https://www.acmicpc.net/problem/10158

package BAEKJOON;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Num10158_개미 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int w = Integer.parseInt(st.nextToken());
        int h = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int p = Integer.parseInt(st.nextToken());
        int q = Integer.parseInt(st.nextToken());
        int t = Integer.parseInt(br.readLine());

        int c = (p + t) % (2 * w);
        int r = (q + t) % (2 * h);

        c = w - Math.abs(w - c);
        r = h - Math.abs(h - r);


        StringBuilder sb = new StringBuilder();
        sb.append(c).append(" ").append(r);
        System.out.println(sb);
        
//        System.out.println(c + " " + r);
    }
}