3349. 최솟값으로 이동하기

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWDTN0cKr1oDFAWD&categoryId=AWDTN0cKr1oDFAWD&categoryType=CODE

SW Expert Academy

 

처음에 완전 탐색으로 접근했다가 시간초과 나왔다.

그 후, 단순하게 시뮬레이션으로 접근하니 풀렸다.

 

<JAVA>

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
 
class Pos {
    Pos(int x, int y) {
        this.x = x;
        this.y = y;
    }
 
    int x, y;
}
 
class Solution {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());
        int N;
        int tx, ty, cx, cy;
        List<Pos> list;
        for (int t = 1; t <= T; ++t) {
            int cnt = 0;
            st = new StringTokenizer(br.readLine(), " ");
            N = Integer.parseInt(st.nextToken(" "));
            N = Integer.parseInt(st.nextToken(" "));
            N = Integer.parseInt(st.nextToken());
            list = new ArrayList<>();
            for (int i = 0; i < N; ++i) {
                st = new StringTokenizer(br.readLine(), " ");
                list.add(new Pos(Integer.parseInt(st.nextToken(" ")), Integer.parseInt(st.nextToken())));
            }
            for (int i = 0; i < N - 1; ++i) {
                tx = list.get(i + 1).x;
                ty = list.get(i + 1).y;
                cx = list.get(i).x;
                cy = list.get(i).y;
                int now = 0;
                while (true) {
                    if (tx == cx && ty == cy) {
                        cnt += now;
                        break;
                    }
                    if (tx < cx && ty < cy) {
                        --cx;
                        --cy;
                    } else if (tx > cx && ty > cy) {
                        ++cx;
                        ++cy;
                    } else if (tx < cx) {
                        --cx;
                    } else if (ty < cy) {
                        --cy;
                    } else if (tx > cx) {
                        ++cx;
                    } else if (ty > cy) {
                        ++cy;
                    }
                    ++now;
                }
            }
            System.out.println("#" + t + " " + cnt);
        }
    }
}

<C++>

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
struct pos {
    int x, y;
};
int main() {
    cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
    int T = 0;
    int W, H, N;
    int x, y, cnt;
    int tx, ty;
    int cx, cy;
    cin >> T;
    vector<pos> v;
    for (int t = 1; t <= T; ++t)
    {
        cnt = 0;
        cin >> W >> H >> N;
        v.clear();
        pos p;
        for (int i = 0; i < N; ++i)
        {
            cin >> x >> y;
            p.x = x;
            p.y = y;
            v.push_back(p);
        }
        for (int i = 0; i < N - 1; ++i)
        {
            tx = v[i + 1].x;
            ty = v[i + 1].y;
            cx = v[i].x;
            cy = v[i].y;
            int now = 0;
            while (true) {
                if (tx == cx && ty == cy)
                {
                    cnt += now;
                    break;
                }
                if (tx < cx && ty < cy)
                {
                    --cx;
                    --cy;
                }
                else if (tx > cx && ty > cy)
                {
                    ++cx;
                    ++cy;
                }
                else if (tx < cx)
                {
                    --cx;
                }
                else if (ty < cy)
                {
                    --cy;
                }
                else if (tx > cx)
                {
                    ++cx;
                }
                else if (ty > cy)
                {
                    ++cy;
                }
                ++now;
            }
        }
        cout << "#" << t << " " << cnt << "\n";
    }
}