Willing

1. 문제 / 난이도 : Gold Ⅳ

www.acmicpc.net/problem/2572

2. 풀이 및 코드 설명

처음에는 가능한 모든 경우의 수를 다 해봐야 하나...? 라고 생각했지만 K의 최대가 10000이고, N의 최대가 1000이어서 모든 경우의 수를 돌면 10000의 1000제곱....빠르게 포기했다. 다른 방법을 생각해보았다.

그래서 그 다음 생각한 방법이 DP를 이용해 푸는 것! 다음과 같은 입력이 들어올 때로 예를 들면,

5
R G R B G
4 5
1 2 R
1 3 G
2 3 G
1 4 R
4 3 B

다섯번째 G 카드를 들고 있을 때 각각의 마을에서 얻는 점수를 계산해보면, DP 배열은 다음과 같다

그 다음, 네번째 B 카드를 들고 있을 때 1번 마을의 경우를 살펴보면 => 1번 마을에서는 2, 3, 4번 마을로 갈 수 있으므로

2번 마을로 가는 경우 = DP[5][2] + 0 = 10 + 0 = 10

3번 마을로 가는 경우 = DP[5][3] + 0 = 10 + 0 = 10

4번 마을로 가는 경우 = DP[5][4] + 0 = 0 + 0 = 0

세가지 경우의 MAX값은 10이다.

(* 빨간색 숫자는 해당 마을로 움직일 때 얻는 점수, B카드를 들고 있을 때 1번에서 2번 마을로 가는 경우에는 R색의 길을 지나므로 점수를 얻기 때문에 0을 더해준다)

마찬가지로 네번째 B 카드를 들고 있을 때 4번 마을의 경우를 살펴보면 => 4번 마을에서는 1, 3번 마을로 갈 수 있으므로

1번 마을로 가는 경우 = DP[5][1] + 0 = 10 + 0 = 10

3번 마을로 가는 경우 = DP[5][3] + 10 = 10 + 10 = 20

두가지 경우의 MAX값은 20이다.

위와 같은 과정을 거쳐 DP배열은 전부 채우면, DP는 다음과 같은 형태가 된다.

원하는 것은 1번 마을에서 첫번째 카드를 들고 있을 때 얻을 수 있는 점수의 최댓값이므로 DP[1][R]이 답이된다.

(1) 설정 및 초기화

# 보드 정보 저장
for _ in range(K):
    i, j, c = sys.stdin.readline().split()
    board[int(i)].append((int(j), c))
    board[int(j)].append((int(i), c))
# dp 배열 초기화
dp = [[0 for _ in range(M + 1)] for _ in range(N+1)]

board[i] : i에서 갈 수 있는 정점과, 그 때 지나는 길의 색이 튜플 형태로 저장되어 있음

(2) DP배열 채우기

for i in range(N-1, -1, -1): # 카드를 하나씩 돌면서
    current_card = cards[i] # 현재 카드
    for j in range(M, 0, -1): # 각 마을을 하나씩 돌면서
        temp = 0
        for k in board[j]: # 해당 마을에서 갈 수 있는 정점의 정보
            node = k[0] # 정점 번호
            vertex = k[1] # 길의 색
            temp = max(dp[i+1][node] + (10 if vertex == current_card else 0), temp) # 모든 경우의 최댓값
        dp[i][j] = temp

3. 전체 코드

import sys

N = int(input())
cards = sys.stdin.readline().split()
M, K = map(int, sys.stdin.readline().split())
board = [[] for _ in range(M + 1)]

for _ in range(K):
    i, j, c = sys.stdin.readline().split()
    board[int(i)].append((int(j), c))
    board[int(j)].append((int(i), c))

dp = [[0 for _ in range(M + 1)] for _ in range(N+1)]

for i in range(N-1, -1, -1):
    current_card = cards[i]
    for j in range(M, 0, -1):
        temp = 0
        for k in board[j]:
            node = k[0]
            vertex = k[1]
            temp = max(dp[i+1][node] + (10 if vertex == current_card else 0), temp)
        dp[i][j] = temp
print(dp[0][1])

1. 문제 / 난이도 : Gold Ⅴ

www.acmicpc.net/problem/1092

2. 풀이 및 코드 설명

하... 분명히 틀린 부분이 없는데 계속 시간초과가 나서 PyPy3로 제출해보니 맞았다...앞으로는 PyPy3로 제출하자....

무거운 화물을 들 수 있는 크레인에게 무거운 화물을 옮기게 하자! 만 기억하면 쉽게 풀리는 문제. 무게 제한이 높은 크레인에게 현재 남아 있는 화물 중 가장 무거운 것을 들게 해야 모든 박스를 옮기는 최소 시간이 나온다.

간단한 코드이기 때문에 코드 블락 단위 설명은 생략.

3. 전체 코드

import sys
N = int(input())
limits = map(int, sys.stdin.readline().split()) # 크레인 별 무게 제한
M = int(input())
packages = map(int, sys.stdin.readline().split()) # 화물 별 무게

# 무게 제한과 화물 무게 전부 내림차순으로 정렬
limits = sorted(limits, reverse=True)
packages = sorted(packages, reverse=True)

# 무게 제한이 제일 높은 크레인도 제일 무거운 화물을 들 수 없는 경우
if packages[0] > limits[0] : 
    print(-1)
    exit()

answer = 0
# 화물이 전부 옮겨질 때까지
while len(packages) > 0:
    answer += 1
    # 무게제한을 돌면서 옮길 수 있는 화물을 옮김
    for l in limits:
        for j in range(len(packages)):
            if l >= packages[j]: # 화물을 옮길 수 있으면
                del packages[j]
                break
print(answer)

1. 문제 / 난이도 : SilverⅡ

www.acmicpc.net/problem/1058

2. 풀이 및 코드 설명

직접 친구이거나, 한 다리 건너서 아는 사람이면 전부 세는 문제. 친구관계를 먼저 설정한 후에 직접 친구인 사람들을 먼저 세고 그 사람들의 친구인 사람들까지 세서 카운트했다.

나랑 직접 친구이고, 한 다리 건너서 하는 친구 일 수도 있기 때문에 중복을 없애기 위해 set을 사용하기로 했다. 그냥 set은 자동으로 정렬이 되지만, 해당 문제는 정렬까지는 필요없고 중복이 없기만 하면 되기 때문에 unordered_set을 사용했다. 

(1) 초기화 및 설정

char temp;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> temp;
			if (temp == 'Y') {
				map[i].push_back(j);
			}
		}
	}

• map[i] : i와 친구인 사람들

(2) unordered_set 사용해서 친구 세기

unordered_set<int> friends; // 직접 친구 + 한 다리 건너서 아는 사람
	for (int i = 0; i < N; i++) {
		for (auto &ele : map[i]) {
			friends.insert(ele); //직접 친구인 사람 추가
			for (auto &f : map[ele]) {
				if (f != i) friends.insert(f); // 그 사람과 친구인 사람 추가
			}
		}
		friends_cnt.push_back(friends.size()); 
		friends.clear();
	}

	sort(friends_cnt.begin(), friends_cnt.end()); // 카운트 정렬 
	cout << friends_cnt[N-1];

• friends : 직접 친구와 한 다리 건너서 아는 사람을 저장하는 set.
• friends_cnt : friends를 다 판별하고 난 뒤, 해당 set의 크기를 저장(set의 크기 = 아는 사람 수)
• 정렬 후 마지막 원소를 출력함으로써 제일 아는 사람이 많은 사람의 지인 수를 출력

3. 전체 코드

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
using namespace std;

vector<int> map[50];
vector<int> friends_cnt;
int N;

int main() {
	cin >> N;
	char temp;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> temp;
			if (temp == 'Y') {
				map[i].push_back(j);
			}
		}
	}

	unordered_set<int> friends;
	for (int i = 0; i < N; i++) {
		for (auto &ele : map[i]) {
			friends.insert(ele);
			for (auto &f : map[ele]) {
				if (f != i) friends.insert(f);
			}
		}
		friends_cnt.push_back(friends.size());
		friends.clear();
	}

	sort(friends_cnt.begin(), friends_cnt.end());
	cout << friends_cnt[N-1];
}

1. 문제 / 난이도 : GoldⅡ

www.acmicpc.net/problem/2623

2. 풀이 및 코드 설명

처음에는 어떻게 풀어야하지...? 하고 고민하다가 결국 알고리즘 분류에 위상정렬이라는 키워드가 있는 것을 보고 간단한 위상정렬 구현으로 쉽게 풀었다.

순서가 정해져 있는 노드들을 전부 방문해야 한다면 => 위상 정렬을 사용할 수 있다는 점을 잊지 말자!

(1) 초기화 및 설정

	cin >> N >> M;
	while (M--) {
		cin >> K;
		int prev;
		for (int i = 0; i < K; i++) {
			int current;
			if (i == 0) cin >> prev; // i가 0이라면 맨 처음 값이므로 prev 초기화
			else {
				cin >> current;
				cnt[current] = cnt[current] + 1; // 진입 vertex 수 cnt 증가
				arr[prev].push_back(current); // prev -> current로 이어진 그래프 생성
				prev = current; // prev 갱신
			}
		}
	}

• arr : 각 노드마다 연결된 노드들의 정보들을 저장
• cnt : 위상정렬을 구현하기 위한 배열. 각 노드당 진입 vertex의 개수를 저장

(2) 큐 초기값

queue<int> q; // 위상정렬 큐
	for (int i = 1; i < N + 1; i++) {
		if (cnt[i] == 0 && visit[i] == 0) { // 아직 방문하지 않았고, 진입 vertex 수가 0이라면
			q.push(i); // 해당 노드 큐에 추가
			visit[i] = 1; // visit값 갱신
		}
	}

(3) 위상정렬

	while (!q.empty()) {
		int current = q.front(); // 현재 노드
		q.pop();
		result.push_back(current); // result 배열에 추가

		for (int i = 0; i < arr[current].size(); i++) {
			cnt[arr[current][i]]--; // 현재 노드와 연결된 노드 모두 진입 vertex 수 하나씩 감소
		}

		for (int i = 1; i < N + 1; i++) {
			if (cnt[i] == 0 && visit[i] == 0) { // 갱신된 노드들 중 진입 vertex 수가 0이고 아직 방문하지 않았다면
				q.push(i);
				visit[i] = 1;
			}
		}
	}

• 큐가 빌 때까지 위상정렬 진행

(4) 출력

	if (result.size() != N) cout << 0;
	else {
		for (int i = 0; i < N; i++) cout << result[i] << endl;
	}

• result 크기와 N이 같지 않다는 것 : 중간에 순환이 생겨 위상정렬이 제대로 이루어지지 않았다는 것 = 순서를 정할 수 없다는 말
• 위의 조건이 아닐때는 result 순서대로 출력

3. 전체 코드

#include <iostream>
#include <queue>
#include <vector>
#include <queue>
using namespace std;

int N, M, K;
vector<vector<int>> arr(1001);
int cnt[1001];
int visit[1001];
vector<int> result;

int main() {
	cin >> N >> M;
	while (M--) {
		cin >> K;
		int prev;
		for (int i = 0; i < K; i++) {
			int current;
			if (i == 0) cin >> prev;
			else {
				cin >> current;
				cnt[current] = cnt[current] + 1;
				arr[prev].push_back(current);
				prev = current;
			}
		}
	}

	queue<int> q;
	for (int i = 1; i < N + 1; i++) {
		if (cnt[i] == 0 && visit[i] == 0) {
			q.push(i);
			visit[i] = 1;
		}
	}
	
	while (!q.empty()) {
		int current = q.front();
		q.pop();
		result.push_back(current);

		for (int i = 0; i < arr[current].size(); i++) {
			cnt[arr[current][i]]--;
		}

		for (int i = 1; i < N + 1; i++) {
			if (cnt[i] == 0 && visit[i] == 0) {
				q.push(i);
				visit[i] = 1;
			}
		}
	}

	if (result.size() != N) cout << 0;
	else {
		for (int i = 0; i < N; i++) cout << result[i] << endl;
	}
}