[☁️ 구름톤 챌린지] 3주차 학습일지 - 1

문제 11. 통증 (2)

dp문제이다. 

dp문제는 일단 한번 쭉 써두고 규칙을 찾아서 푸는 경우가 많은데 이 문제도 역시 마찬가지다. 

여기서 이해하기 어려웠던 것은 dp[i-A]의 경우다.

예를들어, i가 11이고 통증의 사이즈가 2, 7이라면 11 = 2 * 2 + 7로 해결할 수 있다. 

이때, 11 = 2 * 2 + 7 = dp[4] + 1로 나타낼 수 있다.

- dp[4]가 의미하는 바는 11에서 7을 뺐을 때, dp[4]로 계산할 수 있는 것을 말하고

- 1은 2*2 + 7에 있는 7을 말한다.

 

import java.io.*;
import java.util.*;
import java.math.*;

class Main {
	static int N, A, B;
	static int dp[];
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		String str[] = br.readLine().split(" ");
		A = Integer.parseInt(str[0]);
		B = Integer.parseInt(str[1]);
		
		dp = new int[N+1];
		
		for(int i = 0; i <= N; i++) {
			dp[i] = Integer.MAX_VALUE;
		}
		
		dp[0] = 0;
		
		for(int i = 1; i <= N; i++) {
			// i-A가 0보다 크고, 
			if(i-A >= 0 && dp[i-A] != Integer.MAX_VALUE) {
				dp[i] = Math.min(dp[i], dp[i-A] + 1);
			}
			if(i-B >= 0 && dp[i-B] != Integer.MAX_VALUE) {
				dp[i] = Math.min(dp[i], dp[i-B] + 1);
			}
		}
		
		if(dp[N] == Integer.MAX_VALUE)	{
			System.out.println(-1);
		} else {
			System.out.println(dp[N]);
		}
	}
}

 

문제 12. 발전기

문제 지문을 이해하지 못해 처음에는 풀이가 어려웠다.

지문을 이해해보자면 1 덩어리 개수를 뜻한다. 

지문만 이해하면 전형적인 BFS 문제 풀이다.

import java.io.*;
import java.util.*;

class Main {
	static int N;
	static int map[][];
	static int dy[] = {0, 1, 0, -1};
	static int dx[] = {1, 0, -1, 0};
	static int count;
	static Queue<int[]> queue = new LinkedList();
	static boolean visited[][];
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		map = new int[N][N];
		visited = new boolean[N][N];
		
		for(int i = 0; i < N; i++) {
			String str[] = br.readLine().split(" ");
			for(int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(str[j]);
			}
		}
		
		count = 0;
		
		for(int r = 0; r < N; r++) {
			for(int c = 0; c < N; c++) {
				
				if(map[r][c] == 1) {
	 				queue.add(new int[]{r,c});
					count++;
				}

				while(!queue.isEmpty()) {
					int now[] = queue.poll();
					int y = now[0];
					int x = now[1];
					map[y][x] = 2;

					for(int i = 0; i < 4; i++) {
						int ny = y + dy[i];
						int nx = x + dx[i];

						// 범위 밖 이거나 방문했다면
						if(ny < 0 || ny >= N || nx < 0 || nx >= N || map[ny][nx] == 2) {
							continue;
						}
						if(map[ny][nx] == 1) {
							queue.add(new int[]{ny, nx});
							map[ny][nx] = 2;
						}
					}
				}
			}
		}
		System.out.println(count);
	}
}