15685 드래곤 커브

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

15685번: 드래곤 커브

 

문제를 보고 아 이건 배열 돌리고 돌린 배열을 원본에 잘 붙이고 이를 반복하면 되겠다는 생각이 들어 구현을 시작했다. 근데 다시 생각해보면 이렇게 할 경우 플레 4 이상 문제를 풀어본 적은 없지만 아마 그 정도 난이도가 되지 않을까 싶었다. 

돌리고 그 차이만큼 배열을 당겨서 붙여넣고... 결국 한 번 구현했지만 실패하고 답지를 확인했다.

https://velog.io/@skyepodium/백준-15685-드래곤-커브

백준 15685 드래곤 커브

보자마자 너무 놀랐다. 3시간동안 끙끙대던 문제인데 이런 규칙을 이용해 해결할 수 있다니...

삼성 역량테스트 문제는 이런 빡구현 문제가 많아서 참 쉽지 않다...

코드에서 내 아이디어로 작성된건 getAns 말고 없다는 점이 참 슬프다

#include <bits/stdc++.h>
using namespace std;

//????

bool board[103][103];
int dy[]={0,-1,0,1};
int dx[]={1,0,-1,0};
vector<int> dragon;
int end_x, end_y;
int n;

int getAns(){
    int ret=0;
    for(int i=0;i<100;i++)
        for(int j=0;j<100;j++)
            if(board[i][j] && board[i][j+1] && board[i+1][j] && board[i+1][j+1]) ret++;
    return ret;
}

void make_generation(vector<int>&dragon){
    int size = (int)dragon.size();
    for(int i=size-1;i>=0;i--){
        int dir=(dragon[i]+1)%4;
        end_y+=dy[dir];
        end_x+=dx[dir];
        board[end_y][end_x]=true;
        dragon.push_back(dir);
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    while(n--){
        int x,y,d,g; cin>>x>>y>>d>>g;
        dragon.clear();
        board[y][x]=true;
        end_x=x+dx[d]; 
        end_y=y+dy[d];
        board[end_y][end_x]=true;
        dragon.push_back(d);
        for(int i=0;i<g;i++) make_generation(dragon);
    }
    cout<<getAns();
    return 0;
}