BOJ::10875 뱀

시사점

이해(x)

설계, 손 코딩(x)

복잡도

구현(x)

#include<bits/stdc++.h>
#define endl '\n'
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std;
const int dx[]={1, 0, -1, 0}, dy[]={0, 1, 0, -1};
const int MAXN = 1000 + 1;
const int inf = 0x3f3f3f3f;
typedef long long ll;
struct Line{
    int dir;
    int x1, y1, x2, y2;
    Line(){}
    Line(int a, int b, int c, int d) : x1(a), y1(b), x2(c), y2(d){
        if(b == d)
            dir = 0;
        else
            dir = 1;
        set_point();
    }
    void set_point(){
        if(x1 > x2)
            swap(x1, x2);
        if(y1 > y2)
            swap(y1, y2);
    }
};

int L, n;
pair<int,int> turn[MAXN];
vector<Line> line;
void input(){
    cin >> L >> n;
    rep(i, 0, n){
        char ch;
        cin >> turn[i].first >> ch;
        turn[i].second = (ch == 'L' ? -1 : 1);
    }
    turn[n++] = {inf, -1};
    line.push_back(Line(-L-1, -L-1,  L+1,-L-1));
    line.push_back(Line(-L-1,  L+1,  L+1, L+1));
    line.push_back(Line(-L-1, -L-1, -L-1, L+1));
    line.push_back(Line( L+1, -L-1,  L+1, L+1));
}
void simulate(){
    ll ans = 0;
    int x = 0, y = 0, d = 0;
    rep(i, 0, n){
        int t = inf;
        rep(j, 0, line.size()){
            if(line[j].dir == 0){
                if(d == 0){
                    if(y == line[j].y1 && x < line[j].x1)
                        t = min(t, line[j].x1 - x);
                }else if(d == 1){
                    if(line[j].x1 <= x && x <= line[j].x2 && y < line[j].y1)
                        t = min(t, line[j].y1 - y);
                }else if(d == 2){
                    if(y == line[j].y1 && line[j].x2 < x)
                        t = min(t, x - line[j].x2);
                }else{
                    if(line[j].x1 <= x  && x <= line[j].x2 && y > line[j].y1)
                        t = min(t, y - line[j].y1);
                }
            }else{
                if(d == 0){
                    if(line[j].y1 <= y && y <= line[j].y2 && x < line[j].x1)
                        t = min(t, line[j].x1 - x);
                }else if(d == 1){
                    if(line[j].x1 == x && y < line[j].y1)
                        t = min(t, line[j].y1 - y);
                }else if(d == 2){
                    if(line[j].y1 <= y && y <= line[j].y2 && line[j].x1 < x)
                        t = min(t, x - line[j].x1);
                }else{
                    if(line[j].x1 == x && y > line[j].y2)
                        t = min(t, y - line[j].y2);
                }
            }
        }
        if(t <= turn[i].first){
            cout << ans + t << endl;
            return;
        }
        ans += turn[i].first;
        int nx = x + dx[d] * turn[i].first, ny = y+dy[d] * turn[i].first;
        line.push_back(Line(x, y, nx, ny));
        if(turn[i].second == -1)
            d = (d+1) % 4;
        else
            d = (d+3) % 4;
        x = nx, y = ny;
    }
}
void process(){
    input();
    simulate();
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    process();
    return 0;
}

디버깅(x)

좋은 코드

최적화