글 읽기 - 틀렸는데.. 어느 로직에 오류가 있는 지 모르겠습니다.

dokrsky 5년 전 0

제가 생각한 로직은

N-1 번째 세대에서 (y, x)의 커브의 방향을 저장해두고

N-1 번째의 마지막 지점에서 N-1 번째 세대에서 저장한 커브의 방향에 일정한 규칙을 적용하여

N 번째 세대의 커브 지점들을 계산하도록 구현하였습니다.

아래가 그 로직을 적용한 소스인데.. 틀렸다고 나옵니다.

위문제를 검색해보니.. 다른 분들도 로직은 비슷한데 제가 어느부분을 놓쳤는 지 알려주시면 감사하겠습니다!

#include <cstdio>
#include <vector>
#include <utility>

#define MAX 100
#define RIGHT 0
#define UP 1
#define LEFT 2
#define DOWN 3

using namespace std;

bool map[MAX + 1][MAX + 1] = {false, };

int lastX = 0, lastY = 0;
// 오른쪽, 위쪽, 왼쪽, 아래
int dx[4] = {0, -1, 0, 1};
int dy[4] = {1, 0, -1, 0};

void visit(int y, int x) {
    if (x >= 0 && x <= MAX && y >= 0 && y <= MAX && !map[y][x]) {
        map[y][x] = true;
    }
}

void dragonCurve(vector<int> ds, int g) {
    // 방향 정보(nd, next direction)
    int nd = ds[0];
    for (int i = 0 ; i < g; ++i) {
        int l = ds.size();
        for (int j = l-1 ; j >= 0; --j) {
            nd = (ds[j] + 1) % 4;
            lastX = lastX + dx[nd];
            lastY = lastY + dy[nd];
            ds.push_back(nd);
            visit(lastY, lastX);
        }
    }
}

int main()
{
    int n, d, g, result = 0;
    scanf("%d", &n);
    
    for (int i = 0 ; i < n; ++i) {
        scanf("%d %d %d %d", &lastY, &lastX, &d, &g);
        map[lastY][lastX] = true;
        
        vector<int> ds;
        ds.push_back(d);
        
        lastX = lastX + dx[d];
        lastY = lastY + dy[d];
        visit(lastY, lastX);
    
        dragonCurve(ds, g);
    }
    
    for (int i = 0; i <= MAX; ++i) {
        for (int j = 0 ; j <= MAX; ++j) {
            if (map[i][j] && map[i][j + 1] && map[i + 1][j + 1] && map[i + 1][j]) {
                result++;
            }
        }
    }
    
    printf("%d\n", result);
    
    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

틀렸는데.. 어느 로직에 오류가 있는 지 모르겠습니다.

dokrsky 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말