나그네

16567번: 바이너리 왕국 문제 https://www.acmicpc.net/problem/16567 16567번: 바이너리 왕국 첫째 줄에 바이너리 길의 칸의 개수 N, 시련의 개수 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에 N개의 현재 바이너리 길의 상태가 주어진다. 그다음 M개의 줄에 걸쳐서 시련이 주어진다. 이때 0 www.acmicpc.net 풀이 이어져 있는 더러운 칸을 하나의 집합이라 했을 때 몇 개의 집합이 있는지 카운트 수를 유지해 주면 된다. 현재 상태를 입력받을 때 N+2 크기의 배열을 만들어 0번 index와 N+1번 인덱스는 0으로 두고 1~N번 인덱스에 수를 입력받는다. 왼쪽부터 차례로 입력을 받으므로 입력이 더러운 칸일 때, 왼쪽 칸이 깨끗한 칸인 경우..

27866번: 문자와 문자열 문제 https://www.acmicpc.net/problem/27866 27866번: 문자와 문자열 첫째 줄에 영어 소문자와 대문자로만 이루어진 단어 $S$가 주어진다. 단어의 길이는 최대 $1\,000$이다. 둘째 줄에 정수 $i$가 주어진다. ($1 \le i \le \left|S\right|$) www.acmicpc.net 풀이 문자열 S의 i번째 문자를 출력하는 문제다. 문자열 s와 정수 i를 입력받고 s[i-1]을 출력하면 된다. 코드 #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); string s; int i; cin >> s >> i; cout

6497번: 전력난 문제 https://www.acmicpc.net/problem/6497 6497번: 전력난 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들 www.acmicpc.net 풀이 두 집 사이의 거리만큼의 비용이 드는 가로등이 있고 가로등 불이 켜져 있는 도로로만 이동 가능하도록 유지하면서 최소 비용이 들도록 불을 꺼야 하므로 전체 간선의 가중치에서 최소 스패닝 트리(MST)의 가중치를 빼주면 된다. 코드 #include using namespace std; vector p; int find(int x) { if (p[x] != x) p[x] = find..

27939번: 가지 교배 문제 https://www.acmicpc.net/problem/27939 27939번: 가지 교배 키위별의 유전학에 따르면 가지의 교배는 두 가지 서로 다른 방식이 가능하다. 교배란 서로 다른 두 품종으로부터 이전에 존재한 적 없는 하나의 품종을 만들어내는 것이다. P-우선 교배: 흰색과 www.acmicpc.net 풀이 조수들은 P-우선 교배를 하기 때문에 보라색인 가지가 1개라도 섞여있다면 보라색 가지가 배출되고, 키위는 W-우선 교배를 하기 때문에 흰색인 가지가 하나라도 있다면 흰색 가지가 배출된다. 따라서 각 번호의 가지가 P인지 W인지 저장하는 배열을 만들어두고 각 조수가 가진 품종 중에 P가 몇 개인지 센다. P-우선 교배에 따라 P가 0인 경우 W를 1 증가시키고 모..

27880번: Gahui and Soongsil University station 문제 https://www.acmicpc.net/problem/27880 27880번: Gahui and Soongsil University station Soongsil University Station is famous as the deepest station on Seoul Subway Line 7. This station is so deep that the platform is on the B6. Gahui was surprised that she did not reach the platform after more than five minutes from the exit. Gahui wants to www.acmic..

3780번: 네트워크 연결 문제 https://www.acmicpc.net/problem/3780 3780번: 네트워크 연결 입력은 여러 개의 테스트케이스로 주어진다. 입력의 첫 번째 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스에는 기업의 수를 나타내는 N(4 ≤ N ≤ 20,000)이 주어진다. 다음은 몇 www.acmicpc.net 풀이 정점들에 대해 I 쿼리는 두 정점을 연결하고 E 쿼리는 정점에 대해 루트 노드까지의 거리를 출력한다. 유니온 파인드 알고리즘을 사용해 해결했다. 보통의 유니온 파인드와 다른 점은 정점의 부모 노드를 루트 노드로 갱신하는 것이 아니라 각 정점 간 관계를 저장한다. 예를 들어 정점 i와 j를 이으면 p[i] = j 가 된다. 먼저 기본적인 큰 틀은 I ..

4343번: Arctic Network 문제 https://www.acmicpc.net/problem/4343 4343번: Arctic Network The first line of input contains N, the number of test cases. The first line of each test case contains 1 > S >> P; p.resize(P + 1); iota(p.begin(), p.end(), 0); vector edge; vector xy(P + 1); for (int i = 1; i > xy[i].first >> xy[i].second; for (int i = 1; i < P; i++) for (int j = i + 1; j

10775번: 공항 문제 https://www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 풀이 개인적으로 지문 이해가 어려운 문제였다. 각 비행기는 g번 이하의 숫자의 게이트에 도킹이 가능하고 이미 도킹이 되어있는 곳에는 도킹할 수 없다. 비행기가 도킹을 할 수 없다면 공항은 폐쇄된다. 최대한 많은 비행기를 도킹할 때 가능한 도킹 수를 출력하는 문제다. 유니온 파인드 알고리즘을 사용해서 풀었다. 처음에 비행기가 g번 이하의 게..

1005번: ACM Craft 문제 https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 풀이 1516번 문제와 비슷한 문제로 각 건물을 짓는 데는 먼저 지어져야 하는 건물이 있으므로 위상 정렬을 해야 한다. 특정 건물이 완성되기까지 걸리는 시간은 이전 건물이 완성되기까지 걸리는 최대 시간 + 특정 건물을 짓는 시간이다. 그리고 이전 건물에 대해서도 같은 과정을 반복하게 된다. 따라서 DP 테이블을 만들어 (누적 값 + 현재 추가 값)이 최대가..

4195번: 친구 네트워크 문제 https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 풀이 친구 네트워크가 연결될 때마다 네트워크에 연결된 사람의 수를 출력하는 문제다. 각 이름에 대해 번호를 부여하기 위해 map 자료 구조를 사용한다. 만약 map에 이름이 없다면 맵의 사이즈를 번호로 사용하게 한다. 이러면 번호가 0번부터 붙게 된다. 또 N번의 연결이 이루어지는데 각 연결마다 두 명의 이름이 주어지므로 최대 2 × N명의 관계를 받을 ..