글 읽기 - 도중에 맥주가 반쯤 남는다면?

danobti 5년 전 0

문제에는 빈 맥주병을 버리고 새 맥주병으로 채운다고 하셔서, 맥주가 남은 맥주병은 버릴 수 없는줄 알았어요.. 저처럼 생각하신 분은 없나요?

그래서 혹시나 하고 맥주병을 단위로 거리를 쟀는데, 이것 역시 틀렸다고 뜨네요 ㅠㅠ 왜그런거죠?

ceiling 하면 그 거리를 이동해야하는 최소의 정수개의 맥주가 나오니까 이게 20개 이하면 이동할 수 있는 지점이고 아니면 이동할 수 없다고 생각했습니다.

혹시 어느부분이 잘 못된건지 같이 봐주실 수 있나요?

#include <iostream>
using namespace std;
#include <math.h>
#include <queue>
#include <string>
#include <cstring>
#define BEER_PER_DIST 50
#define MAX_BEER 20
#define HOME 0
#define MAX 102
int T;
int adj[MAX][MAX];

int dist(pair<int,int> from, pair<int,int> to) {
    int d = abs(from.first - to.first) + abs(from.second - to.second);
    return ceil( d / BEER_PER_DIST );
}

int main() {
    cin >> T;
    int N;
    pair<int, int> src, dest;
    pair<int, int> seeU[MAX]; // 편의점
    for(int t = 1; t <= T; t++) {
        cin >> N;
        const int DEST = N + 1;
        for(int i = 0; i <= DEST; i++) {
            cin >> seeU[i].first >> seeU[i].second;
        }

        src = seeU[HOME];
        dest = seeU[DEST];

        // 거리 계산, 단위: 맥주
        for(int i = 0; i <= DEST; i++) {
            for(int j = 0;j <= DEST; j++) {
                adj[i][j] = dist(seeU[i], seeU[j]);
            }
        }

        bool visited[MAX];
        memset(&visited, false, sizeof(bool) * MAX);

        queue<int> q; // index
        q.push(HOME);
        bool possible = false;

        while(!q.empty()) {
            auto now = q.front();
            q.pop();

            if(visited[now])
                continue;
            visited[now] = true;

            if(now == DEST) {
                possible = true;
                break;
            }

            for(int i = 0; i <= DEST; i++) {
                if(now == i) continue;
                if(adj[now][i] <= 20) {
                    q.push(i);
                }
            }
        }
        printf("%s\n", possible?"happy":"sad");
    }
}

randoms 5년 전 1

d / 10 이 소수점이 나올까요??

d가 int형이라 그냥 저거 자체가 나머지를 없애버릴것같아요.

danobti 5년 전 0

흠.. 제가 문제를 잘 못 이해한건가요?

집이 0,0 이라 가정하고 편의점1이 20, 15 에 있다고 생각하면,

맨하튼 거리는 35 일테고,

50m마다 맥주하나로 가니까,

맥주로 환산한 거리는 1맥주 아닌가요?

Green55 5년 전 1

d / BEER_PER_DIST 를 먼저 int형으로 계산하고 소수점이 버려진 상태로 ceil에 들어가게 되어 올림 연산이 제대로 시행되지 않습니다.

그리고 실수 오차는 항상 존재하기 때문에, 이렇게 정수만을 이용해서 계산 할 수 있으면 무조건적으로 정수로만 푸시는게 좋습니다.

일단 이 문제에서는 편의점을 들릴 때 마다 20병을 전부 충전 할 수 있다고 가정하고 푸셔도 좋습니다.

최단거리로 간다는 말도 없으니 일부러 돌아가면서 맥주를 남기지 않고 간다고 생각하시면 될거같아요.

그렇다면 굳이 어떤 두 지점이 맥주 몇 병에 해당되는지 계산할 필요가 없어집니다.

중요한건 맥주 20병으로 갈 수 있는 거리 이하인가, 초과인다 겠지요.

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

문제

문제

출처

ICPC

도중에 맥주가 반쯤 남는다면?

danobti 5년 전 0

randoms 5년 전 1

danobti 5년 전 0

Green55 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말