백준) DP, DFS

수익 4097번

---

내가 떠올린 풀이 해설

입력이 많지 않아 BufferedReader보단 Scanner를 사용했습니다. 처음 코드를 작성했을 때 max 값을 0으로 선언을 해주었지만 입력값이 음수일 경우 max 값을 구할 때 max 값이 0이 되므로 max 값을 Integer.MIN_VALUE로 선언해 주어야 합니다. 총수입을 담을 sum 변수를 만들었습니다. 입력의 마지막은 0으로 구분해서 입력 n이 0이면 break 하고 0이 아니면 for 문으로 n 미만까지 for 문을 수행한다. for 문에는 입력 값을 담을 num을 선언해 주었고 입력받은 값을 sum에 누적해서 더합니다. Math.max를 이용해 max와 sum을 비교해 큰 값을 max에 담았습니다. sum의 값이 음수가 되면 sum 값을 0으로 다시 초기화하였습니다.

---

정확한 풀이

import java.util.*;
public class Baek4097 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true) {
			int n = sc.nextInt();
			int max = Integer.MIN_VALUE; 
			int sum = 0;
			if(n == 0) {
				break;
			}
			else {
				for(int i = 0; i < n; i++) {
					int num = sc.nextInt();
					sum += num;                // -3, 1, 10, 8, 3, 11
					max = Math.max(max, sum);  // 0, 1, 10, 10, 10, 11
					if(sum < 0) {
						sum = 0;
					}
				}
				System.out.println(max);
			}
		}
	}
}

---

풀이 2

문제 분류가 다이나믹 프로그래밍이어서 DP로 풀어보려 했는데 방법이 떠오르지 않아 DP를 이용해서 푼 풀이를 가져왔습니다. 위의 코드와 차이점은 배열을 이용해서 현재 i의 값과 직전 값과 현재 i의 값을 더한 게 더 클 때 arr[i]의 값을 직전 값과 현재 i의 값으로 바꿔주는 것입니다. DP의 메모리제이션을 이용해서 해결한 것 같습니다.
https://velog.io/@pss407/%EB%B0%B1%EC%A4%804097-%EC%88%98%EC%9D%B5

[백준]#4097 수익

---

정확한 풀이

import java.util.*;

public class Baek4097 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true) {
			int n = sc.nextInt();
			int max = Integer.MIN_VALUE;
			int sum = 0;
			int[] arr = new int[n];
			if(n == 0) {
				break;
			}
			else {
				for(int i = 0; i < n; i++) {
				        int x = sc.nextInt();
	                                arr[i] = x;
                                        if(i > 0) {
	                                       int y = arr[i-1];
                                               if(x + y > x) {   //직전 값과 현재 i의 값을 더한게 더 클 때
	                                          arr[i] = x + y;
                                               }
	                                 }
	                         }
	                         max = Math.max(max, arr[i]);
			}
			System.out.println(max);
		}
	}
}

---

단지 번호 붙이기 2667번

---

내가 떠올린 풀이 해설

상하좌우를 탐색할 int 배열 dx, dy를 선언합니다. 지도 크기를 입력받을 n, 2차원 배열의 map, DFS의 visit 배열, 총 단지 수를 구하기 위한 total, 각 단지에 속하는 집의 수를 구하기 위해 cnt를 선언해 주었습니다. BufferedReader를 이용해 입력을 받았습니다. map의 입력은 split를 이용해 잘라서 map의 2차원 배열에 넣어 주었습니다.(split("")[i]의 참고 자료: https://crazykim2.tistory.com/549) 전체 map을 탐색하기 위해 이중 for 문을 이용하였고 map의 (i, j)가 1이고 방문하지 않았다면 총 단지 수와 cnt의 수를 늘려주고 DFS를 호출합니다. DFS에서는 상하좌우 탐색을 진행하면서 cnt를 늘려줍니다. 마지막으로 cnt의 값을 List에 담아줍니다. 각 단지 내 집의 수를 오름차순으로 정렬하여 출력해 주어야 하므로 Collections.sort()를 이용해 정렬하였습니다.

---

정확한 풀이

import java.util.*;
import java.io.*;
public class Baek2667 {
	static int[] dx = {1, 0 ,0, -1};
	static int[] dy = {0, 1, -1, 0};
	static int n; // 지도 크기 
	static int[][] map;
	static boolean[][] visit;
	static int total = 0;  // 총 단지 수 
	static int cnt;
	static List<Integer> cnts = new ArrayList<>(); // 각 단지에 속하는 집의 수 
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		map = new int[n][n];
		visit = new boolean[n][n];
		
		String str;
		for(int i = 0; i < n; i++) {
			str = br.readLine();
			for(int j = 0; j < n; j++) {
				map[i][j] = Integer.parseInt(str.split("")[j]);
			}
		}
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				cnt = 0;
				if(map[i][j] == 1 && !visit[i][j]) {
					total++;
					cnt++;
					dfs(i, j);
					cnts.add(cnt);
				}
			}
		}
		System.out.println(total);
		Collections.sort(cnts);
		for(int i = 0; i < cnts.size(); i++) {
			System.out.println(cnts.get(i));
		}
	}

	private static void dfs(int i, int j) {
		visit[i][j] = true;
		for(int k = 0; k < 4; k++) {
			int nx = dx[k] + i;
			int ny = dy[k] + j;
			if(nx >= 0 && nx < n && ny >= 0 && ny < n) {
				if(!visit[nx][ny] && map[nx][ny] == 1) {
					cnt++;
					dfs(nx, ny);
				}
			}
		}
	}
}

---

오늘의 회고

요즘 스터디와 공모전으로 너무 바빠서 코딩 테스트 문제를 풀지 못했더니 많이 까먹은 것 같습니다. 이제 곧 하반기 채용 시작인데 다시 코딩 테스트 공부를 좀 해야겠습니다. 알고리즘 너무 어려워 이번에 알고리즘 스터디에 참여하게 되었는데 다들 실력이 좋으셔서 놀랐습니다. 분발하자