백준: 제 1회 블롭컵 (앞 4문제만 JAVA 풀이)

처음으로 온라인 대회에 참여해 보았다(https://www.acmicpc.net/category/detail/3030).

문제 리스트

 

A: blobnom 

탑의 구조상 2칸 이상 떨어진 블롭을 가져올 수 없다. 따라서, 그리디하게 max(탑의 양 끝의 blob 수, max(i(1~N-2)번째 타워의 blob 수 + min(i-1번째 타워의 blob 수, i+1번째 타워의 blob 수)로 구하면 된다. 첫 번째 문제다보니 가장 쉽다고 느껴지는데, 가장 탑의 양 끝 값 등의 세부 고려 사항이 살짝 있어서 정답률이 마냥 높지는 않다. 나는 3번 틀렸다 ㅎㅎ

코드

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

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] blobs = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			blobs[i] = Integer.parseInt(st.nextToken());
		}
		
		int ans = 0;
		if (N == 1) System.out.println(blobs[0]);
		else if (N == 2) System.out.println(Math.max(blobs[0], blobs[1]));
		else {
			ans = Math.max(ans, blobs[0]);
			for (int i = 1; i < N-1; i++) {
				ans = Math.max(ans, blobs[i] + Math.min(blobs[i-1], blobs[i+1]));
			}
			ans = Math.max(ans, blobs[N-1]);
			
			System.out.println(ans);
		}
	}

}

 

B: blobyum

0부터 K-1번째 index까지의 합을 구하고, 길이가 K인 슬라이딩 윈도우를 N-1번 움직여주면서 들어가는 index값 더하고, 나가는 index값 빼주면서 합의 최댓값을 구한다.

코드

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

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		int ans = 0;
		int sum = 0;
		int[] nums = new int[N];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < K; i++) {
			nums[i] = Integer.parseInt(st.nextToken());
			sum += nums[i];
		}
		ans = sum;
		for (int i = K; i < N; i++) {
			nums[i] = Integer.parseInt(st.nextToken());
		}
		
		for (int i = 0; i < (N-1); i++) {
			sum += (nums[(i+K)%N] - nums[i]);
			ans = Math.max(sum, ans);
		}
		
		System.out.println(ans);
	}

}

 

C: blobblush

원소가 2의 n제곱-1 형태이면 자기 자신만 출력, 아닌 경우는 자기 자신과 합하여 2의 n제곱-1의 형태가 되는 다른 수를 같이 출력하면 된다. 비트마스킹이라면 비트마스킹인데, 그냥 아이디어 떠오르는게 더 중요한 문제인 듯하다.

코드

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long N = sc.nextLong();
		int b = 0;
		while (N >= ((long) 1<<b)) b++;
		if (((long)1<<b)-1 == N) System.out.printf("%d\n%d", 1, N);
		else System.out.printf("2\n%d\n%d", ((long) 1<<b)-1 - N, N);
	}

}

 

 

 

---

여기서부터는 못 푼 문제

 

D: blobaww

주어진 2차원 행렬의 크기나 구조가 '딱봐도 DP'이고 누적합 구하는 거 같긴 했는데, E를 기준으로 S의 누적합, M의 누적합을 구하고 구현하려다보니 O(M^2*N^2) 알고리즘이 나와서 못 풀었다.

다음 날 일어나서 생각해보니, S를 기준으로 생각하면 될 거 같아서 dpE[i+1][j+1]를(코드를 간결하게 적기 위해 i+1, j+1로 설정하였다.) x<=i, y<=j인 곳에 있는 'E'의 개수, dpM[i][j]를 x>=i, y>=j 인 곳에 있는 'M"의 개수로 구한 후 행렬을 순회하면서 (r, c)에서 S가 나오면 해당 S를 포함하면서 만들 수 있는 ESM은 dpE[r+1][c+1]*dpM[r][c] 개이다.

코드

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

public class Main {
	static final long PRIME = 1_000_000_007; 
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int M = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());
		
		int[][] dpE = new int[M+1][N+1];
		int[][] dpM = new int[M+1][N+1];
		long ans = 0;
		
		char[][] matrix = new char[M][N];
		for (int i = 0; i < M; i++) {
			String str = br.readLine();
			for (int j = 0; j < N; j++) {
				matrix[i][j] = str.charAt(j);
			}
		}
		
		// (i, j) 보다 상위(등호 포함)에 있는 E의 개수: dpE[i+1][j+1]
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				dpE[i+1][j+1] = dpE[i][j+1] + dpE[i+1][j] - dpE[i][j];
				if (matrix[i][j] == 'E') dpE[i+1][j+1]++;
			}
		}

		for (int i = M-1; i >= 0; i--) {
			for (int j = N-1; j >= 0; j--) {
				dpM[i][j] = dpM[i+1][j] + dpM[i][j+1] - dpM[i+1][j+1];
				if (matrix[i][j] == 'M') dpM[i][j]++;
			}
		}
		
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				if (matrix[i][j] == 'S') ans += ((long)dpE[i+1][j+1] * dpM[i][j] % PRIME);
			}
			ans %= PRIME;
		}
		
		System.out.println(ans);
	}

}

 

E번부터는 벽이 느껴져서 빠른 포기...ㅎㅎ

 

 

후기

1. 생각보다 재미있다. 

2. 2문제 이상 풀면 솔브닥 배경을 준다고 한다: 개이득

3. 골드4 DP면 막 그렇게 어려운 문제는 아닌데, 막상 보니까 잘 안 풀린다. 꾸준히 하자.