글 읽기 - 20056 문제 질문 드립니다... (자답 + 추가 테케 2개 공유)

hyungang7 3년 전 2

당최 어디가 틀렸는지 모르겠습니다;;

추측하기로는 아마 47~55의 인덱스 부분에 문제가 있지 않을까 싶은데... 해당 부분에서 여러 예시를 가지고 뇌버깅 눈버깅 손버깅을 해보았으나 문제점을 찾지 못했습니다.

부디 도움의 손길 부탁드립니다..

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

class Fireball {
    int r, c, m, s, d;
    boolean f;
    Fireball(int r, int c, int m, int s, int d, boolean f) {
        this.r = r;
        this.c = c;
        this.m = m;
        this.s = s;
        this.d = d;
        this.f = f;
    }
}

public class Main {
    static int n, m, k, ans;
    static boolean flag;
    static ArrayList<Fireball>[] fireballs;

    static int[] rArr = {-1, -1, 0, 1, 1, 1, 0, -1};
    static int[] cArr = {0, 1, 1, 1, 0, -1, -1, -1};

    public static void calculate() {
        for(ArrayList<Fireball> list : fireballs) {
            for(Fireball f : list) {
                ans += f.m;
            }
        }
    }

    public static void process() {
        while(k-- > 0) {
            for(ArrayList<Fireball> list : fireballs) {
                if(list.isEmpty()) continue;  // 해당 좌표에 파이어볼 없음

                for(int i = 0; i < list.size(); i++) {  // i-- 하기 위해 forEach 쓰지 않음
                    Fireball f = list.get(i);
                    if(f.f == flag) continue;  // 이번 턴에 새로 들어온 것이면 또 이동시키면 안 됨

//                    int nr = (f.r + (rArr[f.d] * (f.s % n)) + n) % n;
//                    int nc = (f.c + (cArr[f.d] * (f.s % n)) + n) % n;

                    int nr = f.r + rArr[f.d] * f.s;
                    int nc = f.c + cArr[f.d] * f.s;
                    if(nr >= n) nr %= n;
                    if(nc >= n) nc %= n;
                    if(nr < 0) nr = (n - Math.abs(nr)) % n;
                    if(nc < 0) nc = (n - Math.abs(nc)) % n;

                    f.r = nr;
                    f.c = nc;
                    f.f = flag;
                    fireballs[nr * n + nc].add(f);
                    list.remove(i--);  // 이동을 마친 파이어볼은 현재 좌표에서 삭제
                }
            }

            for(int i = 0; i < fireballs.length; i++) {
                int size = fireballs[i].size();
                if(size < 2) continue;

                // 모든 파이어볼 합침
                int mSum = 0, sSum = 0;
                boolean isEven = true;
                for(int j = 0; j < size; j++) {
                    Fireball f = fireballs[i].get(j);
                    mSum += f.m;
                    sSum += f.s;
                    if(f.d % 2 != 0) isEven = false;  // 하나라도 짝수가 아니라면 1,3,5,7
                }
                int nm = mSum / 5, ns = (sSum / size) % n;
                fireballs[i].clear();  // 나눈 파이어볼은 따로 넣어줄 것임. 기존 것들은 여기서 모두 삭제


                if(nm == 0) continue;  // 질량이 0인 파이어볼은 소멸한다(= 4개로 나눈 게 질량이 0이면 새로 추가하지 않는다)
                int d = 0;
                if(!isEven) d = 1;
                for(int nd = d; nd <= 7; nd+=2) {  // 4개로 나누어져 새로운 값들을 부여받은 파이어볼
                    fireballs[i].add(new Fireball(i/n, i%n, nm, ns, nd, flag));
                }
            }

            flag = !flag;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        fireballs = new ArrayList[n*n];
        for(int i = 0; i < n*n; i++) {
            fireballs[i] = new ArrayList<>();
        }

        for(int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken()) - 1;
            int c = Integer.parseInt(st.nextToken()) - 1;
            int m = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken()) % n;
            int d = Integer.parseInt(st.nextToken());
            Fireball fireball = new Fireball(r, c, m, s, d, true);
            fireballs[r * n + c].add(fireball);
        }

        process();
        calculate();
        System.out.println(ans);
    }
}

hyungang7 3년 전 6

자답입니다. 일단 fireballs는 그냥 map[][] 이차원으로 바꿔서 사용했습니다. 어차피 먹는 칸도 똑같은데 굳이 1차원으로 2차원을 표현할 필요가 없어보여서요.

main에서 s를 입력받을때 %n해서 받는 게 문제였습니다.

저렇게 받을 경우

n == 4, s == 7, s == 1일 때 ns == 4가 되어야 하지만..

s == 3, s == 1로 받게 되어서 ns == 2라는 잘못된 값이 들어옵니다.

이를 수정한 코드가 아래 코드입니다.

추가적으로 테스트케이스 두가지를 공유합니다.

4 6 4
1 1 5 1 1
3 3 5 1 5
1 3 5 1 3
3 1 5 1 7
2 2 5 1 3
3 2 5 1 2

-> 4

4 9 5
3 2 8 5 2
3 3 19 3 4
3 1 7 1 1
4 4 6 4 0
2 1 6 2 5
4 3 9 4 3
2 2 16 1 2
4 2 17 5 3
3 4 3 5 7

-> 33

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

class Fireball {
    int r, c, m, s, d;
    boolean flag;
    Fireball(int r, int c, int m, int s, int d, boolean flag) {
        this.r = r;
        this.c = c;
        this.m = m;
        this.s = s;
        this.d = d;
        this.flag = flag;
    }
}

public class Main {
    static int n, m, k, ans;
    static boolean turnFlag;
    static ArrayList<Fireball>[][] map;
    static int[] rArr = {-1, -1, 0, 1, 1, 1, 0, -1};
    static int[] cArr = {0, 1, 1, 1, 0, -1, -1, -1};

    public static void calculate() {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(map[i][j].isEmpty()) continue;
                for(Fireball f : map[i][j]) {
                    ans += f.m;
                }
            }
        }
    }

    public static void moveBall() {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(map[i][j].isEmpty()) continue;

                for(int idx = 0; idx < map[i][j].size(); idx++) {
                    Fireball f = map[i][j].get(idx);
                    if(f.flag == turnFlag) continue;  // 이번 턴에 이동해서 온 것은 또 이동시키면 안 딤

                    int nr = f.r + rArr[f.d] * (f.s % n);
                    int nc = f.c + cArr[f.d] * (f.s % n);
                    if(nr > 0) nr %= n;
                    if(nc > 0) nc %= n;
                    if(nr < 0) nr = n - Math.abs(nr);
                    if(nc < 0) nc = n - Math.abs(nc);
                    // (f.s % n)을 곱하기 때문에 n-Math.abs()는 반드시 양수 보장

                    f.r = nr;
                    f.c = nc;
                    f.flag = turnFlag;
                    map[nr][nc].add(f);
                    map[i][j].remove(idx--);
                }
            }
        }
    }

    public static void sumAndDivide() {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                int size = map[i][j].size();
                if(size < 2) continue;

                // sum
                int mSum = 0, sSum = 0;
                int oddCnt = 0, evenCnt = 0;
                for(Fireball f : map[i][j]) {
                    mSum += f.m;
                    sSum += f.s;
                    if(f.d % 2 != 0) oddCnt += 1;
                    if(f.d % 2 == 0) evenCnt += 1;
                }
                map[i][j].clear();  // 합쳐진 파이어볼들은 삭제해준다

                // divide
                int nm = mSum/5, ns = sSum/size, d = 1;
                if(nm == 0) continue;  // 질량이 0인 파이어볼은 사라진다
                if(oddCnt == size || evenCnt == size)
                    d = 0;  // 모두 홀수 or 모두 짝수이면 0,2,4,6
                for(int nd = d; nd <= 7; nd+=2) {
                    Fireball f = new Fireball(i, j, nm, ns, nd, turnFlag);
                    map[i][j].add(f);
                }
            }
        }
    }

    public static void process() {
        while(k-- > 0) {
            moveBall();
            sumAndDivide();
            turnFlag = !turnFlag;
        }
        calculate();
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        map = new ArrayList[n][n];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                map[i][j] = new ArrayList<>();
            }
        }

        for(int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken()) - 1;
            int c = Integer.parseInt(st.nextToken()) - 1;
            int m = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            Fireball f = new Fireball(r, c, m, s, d, true);
            map[r][c].add(f);
        }

        process();
        System.out.println(ans);
    }
}

kws8643 1년 전 1

안녕하세요.

이런거 풀 떄 틀린 느낌이 들면

테스트 케이스는 일반적으로 직접 만들어서 체킹을 진행하시나요??

테케를 직접 만드는게 상당히 어려워, 노하우가 있으신지 문의드립니다

저도 계속 찾다가 다른 글은 다 통과했는데, 이 질문 두번째 테케에서 걸렀네요 (감사드립니다)

wlwl1011 6달 전 0

저도 이거 궁금합니다 !! 테스트 케이스를 어떻게 잘 만들 수 있는지 너무 너무 궁금합니다 ..>!

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

문제

문제

출처

ICPC

20056 문제 질문 드립니다... (자답 + 추가 테케 2개 공유)

hyungang7 3년 전 2

hyungang7 3년 전 6

kws8643 1년 전 1

wlwl1011 6달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말