글 읽기 - 어떻게 하면 메모리 초과를 해결할 수 있을까요? (원인은 알고 있습니다.)

dasd412 4년 전 0

질문드리기 앞서 왜 메모리 초과가 나는지는 인지하고 있음을 말씀드립니다...

왜냐하면 어레이 리스트의 인덱스가 최대 2^999까지 담을 수 없기 때문이죠.

일단, 제 풀이를 먼저 설명드리겠습니다.

Painting이란 객체를 만든다. property는 parent(이전에 선택하였던 수의 값), sum(현재 합=이전 합+현재 선택한 수)
그리디 알고리즘으로는 풀 수없기 때문에 모든 경우의 수를 봐야한다고 생각했습니다. 그래서 착안한 것이 complete binary tree 이용입니다.

이전 색깔을 제외한 다른 두 색깔을 '선택'하는 것이기 때문에 complete binary tree형태의 의사 결정 트리 모양과 같다는 것을 생각해냈기 때문입니다.

결론적으로 보면, 의사 결정 트리의 가장 마지막 레벨(트리의 깊이)에서 최솟값이 최소비용임을 알 수 있습니다.

3.제 나름대로 메모리를 줄일려고 노력한 것은 ArrayList 2개 parent와 child를 교대로 쓴 것입니다. 기존 parent값은 필요가 없기 때문에 parent에 기존 child

를 넣고 child는 비워넣는 것 입니다.

@제가 생각한 방법의 문제는 자명합니다. 3을 쓴다고 하더라도 입력크기가 최악의경우 1000인데, 이러면 가장 마지막 레벨의

요소 개수는 2^1000/2=2^999이기 때문에 터지는 것이죠.

어떻게 하면 더욱 효율적으로 풀 수 있을까요?? 답변자분들의 도움 부탁드립니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;




public class Main {
	


	private static class Painting{
		
		int parent;
		int sum;
		
		public Painting(int p, int sum) {
			parent=p;
			this.sum=sum;
		}
		
	}

	public static void main(String[] args) throws IOException{

		
       
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
       
        int n=Integer.parseInt(br.readLine());
        
        int[]red=new int[n];
        int[]green=new int[n];
        int[]blue=new int[n];
       

        
        String str;
        String[]splits;
        
        
        for(int i=0;i<n;i++) {
        	str=br.readLine();
        	splits=str.split(" ");
        	red[i]=Integer.parseInt(splits[0]);
        	green[i]=Integer.parseInt(splits[1]);
        	blue[i]=Integer.parseInt(splits[2]);
        }
        
        long minCost=Math.min(getMinCost(red,green,blue), Math.min(getMinCost(green,red,blue), getMinCost(blue,red,green)));
        
        bw.write(Long.toString(minCost));
        
        br.close();
        bw.close();
	}

	private static long getMinCost(int[] start, int[] other1, int[] other2) {
		// TODO Auto-generated method stub
		
		Painting p;
		int selected;
		int another;
		
		
		
		List<Painting>parent=new ArrayList<Painting>();
		parent.add(new Painting(start[0],start[0]));
		List<Painting>child=new ArrayList<>();
		
		int level=1;
		
		for(int j=1;j<start.length;j++) {
			
			int i=0;
			while(i<level*2) {

				 
				 if(parent.get(i/2).parent==start[j-1]) {
					 selected=other1[j];
				 }else if(parent.get(i/2).parent==other1[j-1]) {
					 selected=other2[j];
				 }else {
					 selected=start[j];
				 }
				 
				 if(selected==other1[j]) {
						another=other2[j];
					}else if(selected==other2[j]) {
						another=start[j];
					}else {
						another=other1[j];
					}
				 

				if(i%2==0) {
				 

				
					p=new Painting(selected, selected+parent.get(i/2).sum);
					child.add(p);
				
				}
				else {

					p=new Painting(another,another+parent.get(i/2).sum);
					child.add(p);
				
				}
				
				
				
				i++;
			}
			parent.clear();
			parent.addAll(child);
			
			child.clear();
			level*=2;
			
		}
		

		
		/* if parent is chosen, then swap parent, o1, o2 <-> start, other1, other2 appropriately
		 * 
		 * 
		 * cost[0][0]=start[0]
		 * 1
		 * cost[1][0]=cost[0][0]+o1[1], cost[1][1]=cost[0][0]+o2[1]
		 * 2
		 * cost[2][0]=cost[1][0]+o1[2], cost[2][1]=cost[1][0]+o2[2]
		 * cost[2][2]=cost[1][1]+o1[2], cost[2][3]=cost[1][1]+o2[2]
		 * 4
		 * ...
		 * 8
		 */

		long min=parent.get(0).sum;
		
		
		
		for(int i=0;i<level;i++) {
			if(min>parent.get(i).sum) {
				min=parent.get(i).sum;
			}
			
		}
		
		
		return min;
	}

	
	
}

nahwasa 4년 전 0

풀이를 보니 저보다 고수신것같아 힌트만 올리고 가옵니다.

일단 올려두신 풀이가 이해가 되지 않아 글쓴이님의 풀이방식에서 더 효율적으로 풀 방법은 잘 모르겠습니다.

다만 너무 어렵게 생각하신게 아닌가 싶습니다.

전 N과 관계없이, 연산을 위한 추가 메모리로 int 3개만 사용했습니다.

dasd412 4년 전 1

답변 감사합니다. :)

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

문제

문제

출처

ICPC

어떻게 하면 메모리 초과를 해결할 수 있을까요? (원인은 알고 있습니다.)

dasd412 4년 전 0

nahwasa 4년 전 0

dasd412 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말