Baekjoon[16235] - 나무 재테크

링크

16235번: 나무 재테크

문제설명

• 시뮬레이션 + 최적화

문제풀이

• 시뮬레이션 + 최적화
• 시간 신경써야함.
  • 나무를 하나하나 저장하는방법->나무 나이가 겹치는 경우 겹치는 나무갯수를 저장하여 효율성 증가

문제코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.StringTokenizer;


public class Main16235 {

    static class Comp implements Comparator<int[]> {
        @Override
        public int compare(int[] o1, int[]o2) {
            // TODO Auto-generated method stub
            return o1[0]-o2[0];
        }
    }
    public static Comp comp = new Comp();

    public static int[][] dir = {
            {-1,-1},
            {-1,0},
            {-1,1},
            {0,1},
            {1,1},
            {1,0},
            {1,-1},
            {0,-1}
    };

    public static int N;
    public static int M;
    public static int K;
    public static int[][] put;
    public static int[][] map;
    public static int[][] n_put;
    public static LinkedList<int[]>[][] tree;

    public static void spring() {

        int lsize;
        int[] ntree;
        int div;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                lsize = tree[i][j].size();
                for (int k = 0; k < lsize; k++) {
                    ntree = tree[i][j].get(k);
//                    양분이 있으면
                    if(ntree[0] <= map[i][j]) {
//                        성장 가능한 나무 갯수
                        div = Math.min(ntree[1], map[i][j]/ntree[0]);
//                        비료먹고
                        map[i][j] -= div*ntree[0];
//                        나이+1
                        tree[i][j].set(k, new int[] {ntree[0]+1,div});
//                        비료 못먹은 나무들 처리
                        n_put[i][j] += (ntree[0]/2)*(ntree[1]-div);
                    }
//                    양분이 없으면
//                    그다음 나무들도 결국 못먹는건 똑같음 왜냐하면 나이가 같거나 많을테니까
//                    근데 굳이 이거 생각해도 속도는 차이없을듯
                    else {
//                        나이/2만큼 다음맵에 추가
                        n_put[i][j] += (ntree[0]/2)*ntree[1];
                        tree[i][j].remove(k);
//                        리스트 제거했으니, 인덱스 수정
                        k--;
                        lsize--;
                    }
                }
            }
        }
    }

    public static void summer() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                map[i][j]+=n_put[i][j];
            }
        }
    }

    public static void autumn() {
        int lsize;
        int tsize;
        int[] ntree;
        int nr;
        int nc;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                lsize = tree[i][j].size();
                for (int k = 0; k < lsize; k++) {
                    ntree = tree[i][j].get(k);
//                    5N 나이인 경우
                    if(ntree[0]%5==0) {
                        puttop:
                        for (int d = 0; d < 8; d++) {
                            nr = i + dir[d][0];
                            nc = j + dir[d][1];
//                            경계 안이면 번식
                            if (nr>=0 && nr<N && nc>=0 && nc<N) {
                                tsize = tree[nr][nc].size();
//                                처음 나무가 1살짜리면 나무갯수 추가
                                if(!tree[nr][nc].isEmpty() && tree[nr][nc].get(0)[0]==1) {
                                    tree[nr][nc].get(0)[1]+=ntree[1];
                                    continue puttop;
                                }
//                                같은 나이대 나무가 없으면 신규 나무 추가
//                                처음원소에 넣으면 자동정렬됨
                                tree[nr][nc].addFirst(new int[] {1,ntree[1]});
                            }
                        }
                    }
                }
            }
        }
    }

    public static void winter() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                map[i][j]+=put[i][j];
            }
        }
    }

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("res/baekjoon/16235.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int ans=0;

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        map = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                map[i][j]=5;
            }
        }

        tree = new LinkedList[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                tree[i][j] = new LinkedList<int[]>();
            }
        }

        n_put = new int[N][N];
        put = new int[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                put[i][j] = Integer.parseInt(st.nextToken());
            }
        }


        int r;
        int c;
        int y;
        int tsize;
        readtop:
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
//            r,c가 1부터 시작임 -> 0부터 시작으로 바꿈
            r = Integer.parseInt(st.nextToken())-1;
            c = Integer.parseInt(st.nextToken())-1;
            y = Integer.parseInt(st.nextToken());
            tsize = tree[r][c].size();
//            같은 나이대 나무가 있으면 나무갯수 추가
            for (int j = 0; j < tsize; j++) {
                if(tree[r][c].get(j)[0]==y) {
                    tree[r][c].get(j)[1]++;
                    continue readtop;
                }
            }
//            같은 나이대 나무가 없으면 신규 나무 추가
            tree[r][c].add(new int[] {y,1});
        }

//        어린나무 정렬
//        처음에만 정렬하면 됨
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                tree[i][j].sort(comp);
            }
        }

        for (int k = 1; k <= K; k++) {
//            봄
            n_put = new int[N][N];
            spring();
//            여름
            summer();
//            가을
            autumn();
//            겨울
            winter();
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                tsize = tree[i][j].size();
                for (int s = 0; s < tsize; s++) {
                    ans+=tree[i][j].get(s)[1];
                }
            }
        }

        System.out.println(ans);
    }
}

아쉬운점

• 디버깅 방식
  • 답은 맞는데 시간초과 나는 코드랑 하나하나 비교하면서 디버깅하면 훨씬 편하게 차이점을 알 수 있다.
  • LinkedList 배열로 문제를 풀어서 디버깅이 좀 귀찮았다. 디버깅할때 주소값을 보여주니...
• O(N) 및 최적화
  • 1000 year * (봄:100 + 여름:100 + 가을:100*8 + 겨울:100) = 10^6 인줄알았다.
    • 왜터지나했음
  • 1000 year * (봄:나무갯수 + 여름:나무갯수 : 가을:나무갯수*8 + 겨울:나무갯수) 로
    • 나무 갯수가 100을 훨씬 초과할 경우가 생긴다. 영양을 100씩 다주면서 꽉꽉 채워넣었을 경우
    • 이 때 시간초과 발생함.
  • 나무갯수를 줄이는 방법이 필요했음.
    • 나이가 같은 나무를 한곳에 묶어서 나무갯수 변수를 추가하면 된다
    • 이 경우 O(N)이 나무가 겹치는 많큼 줄기 때문에 효율적임.
• 나무갯수 변수 추가 후 꼼꼼함이 부족했음
  • 나무 영양 줄 때
    • 성장 가능한 나무 갯수는 현재 가진 나무 갯수를 초과할 수 없다.
    • div = map[i][j]/ntree[0];
    • 이렇게 하면 그냥 현재 가진 나무 갯수를 초과하는 경우가 생김
    • div = Math.min(ntree[1], map[i][j]/ntree[0]);
  • 나무 번식할 때
    • 나무 번식할 경우에도 번식하는 나무 갯수만큼 번식하는것 고려 안했음
    • tree[nr][nc].get(0)[1]+=ntree[1];
    • tree[nr][nc].addFirst(new int[] {1,ntree[1]});

잘한점

• 최적화
  • 나이가 적은 나무순서대로 영양을 공급받는다고 했기에 1인 나무를 추가할 경우 리스트 제일처음에 추가하면 매년 정렬할 필요 없어짐. 최초 입력받을때만 정렬받으면 됨.
  • comp 클래스 전역변수로 생성 후 nested class 생성 안함.
• tree 정보에 생존여부 정보를 넣는 대신 바로 죽이면서 n_map을 생성해서 대체했음.
  • 봄에 바로 처리하면안되니 n_map에 저장 후 여름에 처리하는 방식으로.
  • 굳이 죽은애들 하나하나 따져가면서 또 반복하는것보다 나은 것 같았음.
• 구현만 따지면 50분걸림
  • 물론 최적화하는거 신경쓰고 삽질한거 합치면 3시간은 되는듯