2025 답/해설 없는 최신 코테 풀이 도전 메모기록

개인적으로 오늘 코테를 풀며 느낀점과 메모를 남겨보려한다. 정말...무작정 풀지말고 먼저 문제 조건 이해를 잘 하자느낀다.

다풀ㅇㅓ놓고 문제조건 잘못이해한걸깨달았을때 내모습

참고로 답은 없고 내 풀이가 틀릴 가능성도 있지만(흠) 일단 남겨놓고 예외 있나생각해봐야지,,

오늘하루종일 이 두문제 생각하느라 시간을 다씀...쩝,,.

머리야...

 

 

🟡 첫번째 문제.

문제조건을 잘못이해해서 다풀어놓고 틀린문제.끝나서야깨달음;

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


public class 독립점 {
	public static void main(String[] args) throws IOException {
		// 빠른 입출력을 위해 BufferedReader 사용
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int n = Integer.parseInt(st.nextToken()); // 정점 수
		int m = Integer.parseInt(st.nextToken()); // 간선 수

		// 인접 리스트 생성 (정점 번호 1~n 사용)
		ArrayList<Integer>[] graph = new ArrayList[n + 1];
		for (int i = 1; i <= n; i++) {
			graph[i] = new ArrayList<>();
		}

		// 간선 입력 받기
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			graph[u].add(v);
			graph[v].add(u);
		}

		boolean[] visited = new boolean[n + 1];
		int answer = 0;

		// 모든 정점을 순회하며 아직 방문하지 않은 컴포넌트를 찾는다.
		for (int i = 1; i <= n; i++) { // 해당 그룹 탐색
			if (!visited[i]) {
				// BFS를 이용하여 컴포넌트 내의 정점 수와 간선 수(각 간선은 2번 세어짐)를 구한다.
				int vertexCount = 0; // 정점 수
				int sumDegrees = 0; // 간선 수

				Queue<Integer> queue = new ArrayDeque<>();
				queue.add(i);
				visited[i] = true;

				while (!queue.isEmpty()) {
					int cur = queue.poll();
					vertexCount++;
					sumDegrees += graph[cur].size();

					for (int next : graph[cur]) {
						if (!visited[next]) {
							visited[next] = true;
							queue.add(next);
						}
					}
				}

				// 실제 간선 수 (각 간선은 양쪽에서 카운트되었으므로 2로 나눈다)
				int edgeCount = sumDegrees / 2;

				// 컴포넌트가 1개 정점인 경우 (고립 정점)
				if (vertexCount == 1) {
					answer += 1;
				}
				// 사이클인 경우: 간선 수 == 정점 수 (단, vertexCount > 1)
				else if (edgeCount == vertexCount) {
					answer += vertexCount / 2;  // floor(vertexCount/2)
				}
				// 그 외는 경로인 경우: 간선 수 == vertexCount - 1
				else {
					answer += (vertexCount + 1) / 2;  // ceil(vertexCount/2)
				}
			}
		}

		System.out.println(answer);
	}
}

 

🟡 두번째 문제

너무어렵다고생각된문제. 그냥 시뮬돌리면 시간초과 무조건나는케이스. DP아니면 시간복잡도가 우주로 폭발함.

근데 이중DP연습좀해야겠다.으 낯설어ㅠㅠ

 

풀이순서

 

• 각 화살마다 가능한 점수를 모두 구하기(시뮬레이션).
  • 화살 1: {4, 6, 8, 10}
  • 화살 2: {18, 20, 22, 24}
  • 화살 3: {28}
• DP를 사용하여, 각 화살을 "사용"하거나 "사용하지 않음"을 선택하면서
  가능한 점수 조합과 그에 따른 총 비용을 업데이트.
• 목표 점수 28점을 만들 수 있는 최소 비용은 최종 계산.

 

 

+보충설명..

2 3 28

4 6

8 10

1 2 10

으로 주어질때 풀이를 예시로 살펴보며 이해해보자 ㅎㅎ

 

DP 배열의 정의:

• dp[i][s]“첫 i개의 화살까지 고려하여, 정확히 s점을 만들 때의 최소 비용”

초기 상태:

• dp[0][0] = 0 (화살을 하나도 사용하지 않아 0점을 만드는 비용은 0)
• 나머지는 매우 큰 값(INF)으로 초기화

[A] 화살 1 처리 (i = 1)

• (1) 화살 1을 사용하지 않는 경우:→ dp[1][0] = 0
• dp[1][s]는 dp[0][s]의 값을 그대로 가져옴.
• (2) 화살 1을 사용하는 경우:
  • 이전 상태에서 s = 0 (dp[0][0] = 0)에서 출발하여,
    • 옵션 4 → 새 점수: 0 + 4 = 4, 비용: 0 + 1 = 1 → dp[1][4] = 1
    • 옵션 6 → 새 점수: 6, 비용: 1 → dp[1][6] = 1
    • 옵션 8 → 새 점수: 8, 비용: 1 → dp[1][8] = 1
    • 옵션 10 → 새 점수: 10, 비용: 1 → dp[1][10] = 1
• 화살 1의 각 옵션을 고려. (이때, 사용 비용은 B[1] = 1)
• 결과:(나머지 점수는 아직 INF)
• dp[1][0] = 0, dp[1][4] = 1, dp[1][6] = 1, dp[1][8] = 1, dp[1][10] = 1

---

[B] 화살 2 처리 (i = 2)

• (1) 화살 2를 사용하지 않는 경우:→ dp[2][0] = 0, dp[2][4] = 1, dp[2][6] = 1, dp[2][8] = 1, dp[2][10] = 1
• dp[2][s]는 dp[1][s]의 값을 그대로 복사.
• (2) 화살 2를 사용하는 경우:이전 dp[1]에서 가능한 s값에 화살 2의 옵션을 추가합니다.
  • 출발 s = 0 (dp[1][0] = 0):
    • 옵션 18 → 새 점수: 0 + 18 = 18, 비용: 0 + 2 = 2 → dp[2][18] = 2
    • 옵션 20 → 새 점수: 20, 비용: 2 → dp[2][20] = 2
    • 옵션 22 → 새 점수: 22, 비용: 2 → dp[2][22] = 2
    • 옵션 24 → 새 점수: 24, 비용: 2 → dp[2][24] = 2
  • 출발 s = 4 (dp[1][4] = 1):
    • 옵션 18 → 새 점수: 4 + 18 = 22, 비용: 1 + 2 = 3→ dp[2][22] = min(현재 dp[2][22]인 2, 3) = 2
    • 옵션 20 → 4 + 20 = 24, 비용: 3 → dp[2][24] = min(2, 3) = 2
    • 옵션 22 → 4 + 22 = 26, 비용: 3 → dp[2][26] = 3
    • 옵션 24 → 4 + 24 = 28, 비용: 3 → dp[2][28] = 3
  • 출발 s = 6 (dp[1][6] = 1):
    • 옵션 18 → 6 + 18 = 24, 비용: 1 + 2 = 3 → dp[2][24] = min(2, 3) = 2
    • 옵션 20 → 6 + 20 = 26, 비용: 3 → dp[2][26] = min(3, 3) = 3
    • 옵션 22 → 6 + 22 = 28, 비용: 3 → dp[2][28] = min(3, 3) = 3
    • 옵션 24 → 6 + 24 = 30, 그런데 30은 목표 점수 28을 초과 → 무시
  • 출발 s = 8 (dp[1][8] = 1):
    • 옵션 18 → 8 + 18 = 26, 비용: 3 → dp[2][26] = 3
    • 옵션 20 → 8 + 20 = 28, 비용: 3 → dp[2][28] = min(3, 3) = 3
    • 옵션 22와 24 → 결과가 30 이상 → 무시
  • 출발 s = 10 (dp[1][10] = 1):
    • 옵션 18 → 10 + 18 = 28, 비용: 1 + 2 = 3 → dp[2][28] = min(3, 3) = 3
    • 다른 옵션은 30 이상이므로 무시
• 화살 2의 옵션는 {18, 20, 22, 24}이며, 사용 비용은 B[2] = 2.
• 결과:
• 중요한 부분은 dp[2][28] = 3, 즉 화살 1과 화살 2를 적절히 사용해서 28점을 만드는 최소 비용이 3임.

---

[C] 화살 3 처리 (i = 3)

• (1) 화살 3을 사용하지 않는 경우:→ 이미 dp[2][28] = 3이 있으므로, dp[3][28]도 우선 3.
• dp[3][s]는 dp[2][s]의 값을 복사.
• (2) 화살 3을 사용하는 경우:
  • 만약 이전 상태에서 s = 0 (dp[2][0] = 0)라면,그러면 dp[3][28] = min(현재 3, 10) = 3.
  • 새 점수: 0 + 28 = 28, 비용: 0 + 10 = 10.
  • 다른 s값에서 시작하면 비용은 더 커지므로, 최소 비용은 그대로 3.
• 화살 3의 옵션는 {28}이며, 사용 비용은 B[3] = 10.
• 최종 결과: dp[3][28] = 3

이와 같이, 각 화살의 가능한 점수 옵션을 미리 계산한 뒤, DP를 사용하여 각 화살을 “사용”하거나 “사용하지 않음”을 선택하면서 목표 점수 28을 만들 수 있는 최소 비용을 구하는 방식으로 문제를 해결.

 

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

public class 과녁판 {
	public static void main(String[] args) throws Exception {
		// 입력 처리
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken()); // 격자 크기 (N×N)
		int K = Integer.parseInt(st.nextToken()); // 화살 개수 (굵기 1,2,...,K)
		int P = Integer.parseInt(st.nextToken()); // 목표 점수

		int[][] grid = new int[N][N];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				grid[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		// 화살 발사 비용 (1-indexed)
		int[] B = new int[K + 1];
		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= K; i++) {
			B[i] = Integer.parseInt(st.nextToken());
		}

		// 각 화살별로 가능한 점수 옵션을 미리 계산
		// arrowOptions[i]에는 굵기 i인 화살을 맞추었을 때 얻을 수 있는 점수의 가능한 값들을 저장 (중복 제거)
		ArrayList<Integer>[] arrowOptions = new ArrayList[K + 1];
		for (int arrow = 1; arrow <= K; arrow++) {
			arrowOptions[arrow] = new ArrayList<>();
			HashSet<Integer> set = new HashSet<>();
			// 격자의 모든 칸 (x, y)를 중심으로 고려
			for (int x = 0; x < N; x++) {
				for (int y = 0; y < N; y++) {
					int score = 0;
					// 맨해튼 거리 (arrow - 1) 이하인 모든 칸의 점수 합산
					for (int u = 0; u < N; u++) {
						for (int v = 0; v < N; v++) {
							if (Math.abs(u - x) + Math.abs(v - y) < arrow) {
								score += grid[u][v];
							}
						}
					}
					set.add(score);
				}
			}
			arrowOptions[arrow].addAll(set);
		}

		// DP를 이용하여 정확히 P점을 만드는 최소 비용 계산
		// dp[i][s]: 첫 i개의 화살까지 고려하여 s점을 만드는 최소 총 비용
		int INF = Integer.MAX_VALUE / 2;
		int[][] dp = new int[K + 1][P + 1];
		for (int i = 0; i <= K; i++) {
			Arrays.fill(dp[i], INF);
		}
		dp[0][0] = 0;

		// 화살 1부터 K까지 순차적으로 고려
		for (int i = 1; i <= K; i++) {
			// 화살 i를 사용하지 않는 경우: 이전 상태 그대로 복사
			for (int s = 0; s <= P; s++) {
				dp[i][s] = Math.min(dp[i][s], dp[i - 1][s]);
			}

			// 화살 i를 사용하는 경우: 가능한 옵션(획득 점수)을 모두 고려
			for (int s = 0; s <= P; s++) {
				if (dp[i - 1][s] != INF) {
					for (int option : arrowOptions[i]) {
						int newScore = s + option;
						if (newScore <= P) {
							dp[i][newScore] = Math.min(dp[i][newScore], dp[i - 1][s] + B[i]);
						}
					}
				}
			}
		}

		// 정답 출력: 정확히 P점을 만드는 최소 비용, 불가능하면 -1 출력
		System.out.println(dp[K][P] >= INF ? -1 : dp[K][P]);
	}
}