글 읽기 - 전체 테스트케이스는 맞지만 런타임에러가 납니다.

pkgonan 7년 전 0

안녕하세요

14226 이모티콘 문제

런타임 에러가 어디서 발생하는지 도움을 구하고싶습니다..

최근 BFS 문제만 집중적으로 푸는데 자꾸 런타임 문제가 발생하네요

2~1000까지의 인풋에 대한 테스트 케이스 정답은 전부 돌려봤는데

로컬상에서 정답으로 나옵니다.

런타임 에러는 어디서 발생하는 것일지 도움 부탁드립니다..

아래는 인풋에 대한 아웃풋 정답 리스트입니다.

인풋 아웃풋(답)

2 2
3 3
4 4
5 5
6 5
7 7
8 6
9 6
10 7
11 8
12 7
13 10
14 9
15 8
16 8
17 9
18 8
19 10
20 9
21 10
22 10
23 10
24 9
25 10
26 10
27 9
28 11
29 11
30 10
31 11
32 10
33 11
34 11
35 11
36 10
37 13
38 12
39 12
40 11
41 13
42 12
43 13
44 12
45 11
46 12
47 12
48 11
49 13
50 12
51 12
52 12
53 12
54 11
55 13
56 13
57 13
58 13
59 13
60 12
61 14
62 13
63 13
64 12
65 14
66 13
67 14
68 13
69 13
70 13
71 13
72 12
73 15
74 14
75 13
76 14
77 14
78 13
79 14
80 13
81 12
82 15
83 15
84 14
85 14
86 15
87 14
88 14
89 14
90 13
91 15
92 14
93 14
94 14
95 14
96 13
97 16
98 15
99 14
100 14
101 15
102 14
103 15
104 14
105 14
106 14
107 14
108 13
109 16
110 15
111 16
112 15
113 16
114 15
115 15
116 15
117 15
118 15
119 15
120 14
121 17
122 16
123 16
124 15
125 15
126 15
127 15
128 14
129 16
130 15
131 16
132 15
133 16
134 15
135 14
136 15
137 16
138 15
139 16
140 15
141 15
142 15
143 15
144 14
145 16
146 17
147 16
148 16
149 16
150 15
151 17
152 16
153 15
154 16
155 16
156 15
157 17
158 16
159 15
160 15
161 15
162 14
163 18
164 17
165 16
166 17
167 17
168 16
169 17
170 16
171 16
172 17
173 17
174 16
175 16
176 16
177 16
178 16
179 16
180 15
181 18
182 17
183 17
184 16
185 17
186 16
187 17
188 16
189 16
190 16
191 16
192 15
193 19
194 18
195 17
196 17
197 17
198 16
199 17
200 16
201 17
202 17
203 17
204 16
205 18
206 17
207 16
208 16
209 17
210 16
211 17
212 16
213 16
214 16
215 16
216 15
217 18
218 18
219 18
220 17
221 18
222 17
223 18
224 17
225 16
226 18
227 18
228 17
229 18
230 17
231 17
232 17
233 17
234 16
235 17
236 17
237 17
238 17
239 17
240 16
241 17
242 16
243 15
244 18
245 18
246 18
247 18
248 17
249 18
250 17
251 18
252 17
253 18
254 17
255 17
256 16
257 19
258 18
259 18
260 17
261 17
262 18
263 18
264 17
265 17
266 18
267 17
268 17
269 17
270 16
271 18
272 17
273 18
274 18
275 18
276 17
277 19
278 18
279 17
280 17
281 18
282 17
283 18
284 17
285 17
286 17
287 17
288 16
289 19
290 18
291 19
292 19
293 19
294 18
295 18
296 18
297 17
298 18
299 18
300 17
301 20
302 19
303 18
304 18
305 18
306 17
307 19
308 18
309 18
310 18
311 18
312 17
313 19
314 18
315 17
316 18
317 18
318 17
319 18
320 17
321 17
322 17
323 17
324 16
325 19
326 20
327 19
328 19
329 19
330 18
331 20
332 19
333 19
334 19
335 19
336 18
337 20
338 19
339 19
340 18
341 19
342 18
343 20
344 19
345 18
346 19
347 19
348 18
349 19
350 18
351 18
352 18
353 19
354 18
355 18
356 18
357 18
358 18
359 18
360 17
361 21
362 20
363 20
364 19
365 20
366 19
367 19
368 18
369 19
370 19
371 19
372 18
373 20
374 19
375 18
376 18
377 19
378 18
379 19
380 18
381 18
382 18
383 18
384 17
385 19
386 20
387 19
388 20
389 19
390 18
391 20
392 19
393 19
394 19
395 19
396 18
397 20
398 19
399 19
400 18
401 19
402 18
403 19
404 18
405 17
406 19
407 19
408 18
409 21
410 20
411 19
412 19
413 19
414 18
415 19
416 18
417 19
418 19
419 19
420 18
421 20
422 19
423 18
424 18
425 19
426 18
427 19
428 18
429 18
430 18
431 18
432 17
433 21
434 20
435 19
436 20
437 21
438 20
439 20
440 19
441 19
442 20
443 20
444 19
445 19
446 20
447 19
448 19
449 19
450 18
451 21
452 20
453 20
454 20
455 20
456 19
457 20
458 19
459 18
460 19
461 20
462 19
463 20
464 19
465 19
466 19
467 19
468 18
469 20
470 19
471 20
472 19
473 20
474 19
475 19
476 19
477 18
478 19
479 19
480 18
481 20
482 19
483 18
484 18
485 18
486 17
487 21
488 20
489 21
490 20
491 21
492 20
493 21
494 20
495 19
496 19
497 20
498 20
499 20
500 19
501 20
502 20
503 20
504 19
505 20
506 20
507 20
508 19
509 20
510 19
511 19
512 18
513 19
514 21
515 20
516 20
517 21
518 20
519 20
520 19
521 20
522 19
523 21
524 20
525 19
526 20
527 20
528 19
529 20
530 19
531 19
532 20
533 20
534 19
535 19
536 19
537 19
538 19
539 19
540 18
541 21
542 20
543 20
544 19
545 21
546 20
547 21
548 20
549 20
550 20
551 20
552 19
553 21
554 21
555 20
556 20
557 20
558 19
559 20
560 19
561 20
562 20
563 20
564 19
565 21
566 20
567 19
568 19
569 20
570 19
571 20
572 19
573 19
574 19
575 19
576 18
577 22
578 21
579 21
580 20
581 22
582 21
583 22
584 21
585 20
586 21
587 21
588 20
589 21
590 20
591 20
592 20
593 20
594 19
595 20
596 20
597 20
598 20
599 20
600 19
601 22
602 21
603 20
604 21
605 21
606 20
607 21
608 20
609 20
610 20
611 20
612 19
613 22
614 21
615 21
616 20
617 21
618 20
619 21
620 20
621 19
622 20
623 20
624 19
625 20
626 21
627 20
628 20
629 20
630 19
631 21
632 20
633 20
634 20
635 20
636 19
637 21
638 20
639 19
640 19
641 20
642 19
643 20
644 19
645 19
646 19
647 19
648 18
649 21
650 20
651 21
652 22
653 22
654 21
655 21
656 21
657 21
658 21
659 21
660 20
661 23
662 22
663 21
664 21
665 21
666 20
667 22
668 21
669 21
670 20
671 21
672 20
673 21
674 20
675 19
676 21
677 22
678 21
679 21
680 20
681 21
682 21
683 21
684 20
685 21
686 22
687 21
688 21
689 21
690 20
691 22
692 21
693 20
694 21
695 21
696 20
697 22
698 21
699 20
700 20
701 20
702 19
703 21
704 20
705 20
706 21
707 21
708 20
709 21
710 20
711 20
712 20
713 21
714 20
715 20
716 20
717 20
718 20
719 20
720 19
721 22
722 21
723 20
724 21
725 20
726 19
727 20
728 19
729 18
730 22
731 22
732 21
733 22
734 21
735 21
736 20
737 22
738 21
739 22
740 21
741 21
742 21
743 21
744 20
745 21
746 22
747 21
748 21
749 21
750 20
751 21
752 20
753 21
754 21
755 21
756 20
757 22
758 21
759 21
760 20
761 21
762 20
763 21
764 20
765 20
766 20
767 20
768 19
769 22
770 21
771 22
772 22
773 22
774 21
775 21
776 22
777 21
778 21
779 21
780 20
781 22
782 21
783 20
784 21
785 22
786 21
787 22
788 21
789 21
790 21
791 21
792 20
793 22
794 21
795 20
796 21
797 22
798 21
799 21
800 20
801 20
802 21
803 21
804 20
805 20
806 21
807 20
808 20
809 20
810 19
811 22
812 21
813 21
814 21
815 21
816 20
817 23
818 22
819 21
820 22
821 22
822 21
823 22
824 21
825 21
826 21
827 21
828 20
829 22
830 21
831 21
832 20
833 22
834 21
835 22
836 21
837 20
838 21
839 21
840 20
841 23
842 22
843 21
844 21
845 21
846 20
847 21
848 20
849 21
850 21
851 21
852 20
853 22
854 21
855 20
856 20
857 21
858 20
859 21
860 20
861 20
862 20
863 20
864 19
865 22
866 23
867 22
868 22
869 22
870 21
871 23
872 22
873 22
874 22
875 21
876 22
877 23
878 22
879 22
880 21
881 22
882 21
883 23
884 22
885 21
886 22
887 22
888 21
889 22
890 21
891 20
892 22
893 22
894 21
895 21
896 21
897 21
898 21
899 21
900 20
901 24
902 23
903 23
904 22
905 23
906 22
907 23
908 22
909 21
910 22
911 22
912 21
913 23
914 22
915 21
916 21
917 21
918 20
919 22
920 21
921 22
922 22
923 22
924 21
925 22
926 22
927 21
928 21
929 22
930 21
931 22
932 21
933 21
934 21
935 21
936 20
937 23
938 22
939 22
940 21
941 22
942 21
943 22
944 21
945 20
946 22
947 22
948 21
949 22
950 21
951 21
952 21
953 21
954 20
955 21
956 21
957 21
958 21
959 21
960 20
961 22
962 21
963 20
964 21
965 21
966 20
967 21
968 20
969 20
970 20
971 20
972 19
973 23
974 23
975 22
976 22
977 24
978 23
979 23
980 22
981 22
982 23
983 23
984 22
985 22
986 23
987 22
988 22
989 22
990 21
991 22
992 21
993 23
994 22
995 22
996 22
997 23
998 22
999 22
1000 21

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static int S, MIN = Integer.MAX_VALUE;
    static boolean[][][] visited;

    public static void main(String[] args) throws IOException {
        init();
        BFS();
    }

    static void BFS(){
        Queue<A> Q = new LinkedList();
        Q.add(new A(1, 0, 0));
        visited[1][0][0] = true;

        while(!Q.isEmpty()) {
            A now = Q.poll();

            if(now.M == S) MIN = Math.min(MIN, now.T);

            if(now.M < S) {
                // 1번 연산 : 현재 화면의 갯수를 클립보드에 저장
                if(now.T+1 <= S) {
                    if(now.M != now.C && !visited[now.M][now.M][now.T+1]) {
                        Q.add(new A(now.M, now.M, now.T+1));
                        visited[now.M][now.M][now.T+1] = true;
                    }

                    // 2번 연산 : 클립보드의 갯수를 모니터에 더해
                    if (now.C != 0 && now.M+now.C <= S && !visited[now.M+now.C][now.C][now.T+1]) { // 클립보드가 비어있지 않을때 붙여넣기 가능
                        Q.add(new A(now.M+now.C, now.C, now.T+1));
                        visited[now.M+now.C][now.C][now.T+1] = true;
                    }

                    // 3번 연산 : 화면값을 감소시켜
                    if (now.M-1 >= 1 && now.T+1 < MIN && !visited[now.M-1][now.C][now.T+1]) {
                        Q.add(new A(now.M-1, now.C, now.T+1));
                        visited[now.M-1][now.C][now.T+1] = true;
                    }
                }
            }
            else {
                if(now.T+1 <= S) {
                    // 3번 연산 : 화면값을 감소시켜
                    if (now.M-1 >= 1 && now.T+1 < MIN && !visited[now.M-1][now.C][now.T+1]) {
                        Q.add(new A(now.M-1, now.C, now.T+1));
                        visited[now.M-1][now.C][now.T+1] = true;
                    }
                }
            }
        }
        System.out.println(MIN);
    }

    static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        S = Integer.parseInt(br.readLine());
        visited = new boolean[S+1][S+1][S+1];
    }

    static class A {
        int M, C, T;
        public A(int M, int C, int T) { this.M = M; this.C = C; this.T = T; }
    }
}

pkgonan 7년 전 0

자문 자답입니다.

해결하였습니다.

static boolean[][][] visited;

visited 배열을 3차원으로 선언하고 visited[모니터값][클립보드값][시간초값] 을 각각 넣어서 했었는데

static boolean[][] visited;

2차원 배열로 변경하고 visited[모니터값][클립보드값] 으로 변경하니 런타임 에러가 발생하지 않네요.

메모리 때문에 도중에 런타임 에러가 발생한것으로 사료되는데...

문제 상에는 메모리가 512메가 바이트까지 가능하다고 나와있습니다.

boolean 값이 1비트 이기에 1000짜리 3차원 배열로 선언하면 1000 * 1000 * 1000

즉, 1,000,000,000 비트

즉, 125,000,000 바이트

즉, 122,070 킬로 바이트

즉, 119 메가 바이트

총 512 메가중 120메가 정도의 값을 3차원 배열로 선언한걸로만으로 먹어버렸고

큐에 동적으로 넣으면서 맥스 512 메가를 초과하게 되어 런타임 에러가 발생한게 아닐까 생각하고 있습니다.

제 생각이 틀리다면 조언 부탁드리겠습니다~!

감사합니다.

pkgonan 7년 전 1

추가 생각..

저와 같은 경험을 하는 분들이 계실까 남깁니다..

boolean 형이 true 혹은 false이기에 겨우 1비트라 3차원 배열을 해도 얼마 메모리를 안잡아 먹겠거니.. 생각했었는데

120메가라니 충격적으로 많이 잡아 먹네요..

메모리 계산을 잘 하는것도 상당히 중요한 역량 같습니다.

런타임 에러가 발생하시는 분들

1. 입력값이 정확히 원하는 자료형태로 들어오는지 검사해본다.

2. 배열의 인덱스 범위를 초과하는지 검사해본다.

3. 메모리가 초과하는지 검사해본다.

이렇게 하나씩 테스트해보시는게 좋을 것 같습니다. 감사합니다

rlaalswo01 6년 전 0

다 아시겠지만 한 가지 의견 달자면,

너비 우선 탐색에선 같은 곳을 최초 방문한 이후에 다시 도착하지 않도록 하는 것이기 때문에,

visited 배열은 2차원이면 충분합니다. (시간차원 제외)

오히려 시간차원이 있다면 같은 곳을 반복해서 방문할 것 같아요.

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

문제

문제

출처

ICPC

전체 테스트케이스는 맞지만 런타임에러가 납니다.

pkgonan 7년 전 0

pkgonan 7년 전 0

pkgonan 7년 전 1

rlaalswo01 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말