백준 3020번 자바 ☆

문제

https://www.acmicpc.net/problem/3020

3020번: 개똥벌레

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main3020 {
	
	static int N,H;
	static int[][] cave;
	static int[] stalactite;
	static List<Integer> list = new ArrayList<Integer>();

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		H = sc.nextInt();
		cave = new int[H][N];
		stalactite = new int[N];
		
		for (int i=0; i<N; i++) {
			stalactite[i] = sc.nextInt();
		}
		
		for (int i=0; i<N; i++) {
			if (i%2 == 0) {
				for (int k=H-1; k>=H-stalactite[i]; k--) {
					cave[k][i] = 1;
				}
			} else {
				for (int k=0; k<stalactite[i]; k++) {
					cave[k][i] = 1;
				}
			}
		}
		
		int test = 0;
		
		for (int i=0; i<H; i++) {
			int count = 0;
			for (int j=0; j<N; j++) {
				if (cave[i][j] == 1) {
					count++;
				} 
			}
			list.add(count);
		}
		
		Collections.sort(list);
		
		System.out.println(list.get(0)+" "+Collections.frequency(list, list.get(0)));
	}
}

import java.util.Scanner;

public class Main3020_1 {
	
	static int N,H;
	static int[] stalacmite; // 석순
	static int[] stalactite; // 종유석
	static int min;
	static int cnt;

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		H = sc.nextInt();
		stalactite = new int[H];
		stalacmite = new int[H];
		min = N;
		
		for (int i=0; i<N/2; i++) {
			stalacmite[sc.nextInt()]++;
			stalactite[sc.nextInt()]++;
		}
		
		for (int i=1; i<H; i++) {
			stalacmite[i] += stalacmite[i-1];
			stalactite[i] += stalactite[i-1];
		}
		
		for (int i=1; i<=H; i++) {
			int sum = 0;
			sum = stalacmite[H-1] - stalacmite[i-1] + stalactite[H-1] - stalactite[H-i];
			
			if (min > sum) {
				min = sum;
				cnt = 1;
			} else if (min == sum) {
				cnt++;
			}
		}
		
		System.out.println(min + " " + cnt);
		
	}
}

1. 첫번째 코드는 메모리초과 발생. 메모리 초과가 아니면 시간 초과가 발생했을 것이다. 처음 접근을 2차원 배열로해서 그런지 2차원 배열안에 계속 갇혀서 생각을 다른쪽으로 해보지 못했다.

 

2. 이번에도 다른 글들을 참고해서 다시 알고리즘을 구성했다. 일단 내가 가장 놓친 중요포인트는 석순,종유석 배열의 값에 직접 각각의 높이를 입력하려 했던 것이다. 각 배열의 인덱스에 높이를 넣고 그 값을 개수로 저장해야했다. 그 다음은 개똥벌레의 구간이 밑에서 부터 올라가기에 종유석 구간합 부분에서 주의해줘야 한다.

 

3. 사실 이전에도 배열의 인덱스에 값을 저장하는 방법으로 푸는 문제들이 있었지만 이번에도 그런쪽으로 생각을 못했다. 

앞으로도 많은 반복이 필요하다.