빅맥좋아요

https://www.acmicpc.net/problem/1738 1738번: 골목길 첫째 줄에 골목길들이 교차하는 지점의 개수 n (2 ≤ n ≤ 100)과 골목길의 개수 m (1 ≤ m ≤ 20,000) 이 차례로 주어진다. 이어지는 m개의 행에 각각의 골목길을 나타내는 세 정수 u, v, w가 차례로 www.acmicpc.net 백준 1738번 골목길 문제를 풀었다. 특정 노드에서 특정 노드로 감 && 간선에 음의 가중치가 있음 -> 벨만 포드로 풀어야 겠다고 생각했다. 문제의 입력에서 cost에 -를 붙여서 음의 사이클 문제로 바꿨다. 문제를 풀기 위해 어떤 경우에 -1을 출력하고 어떤 경우에 경로를 출력하는지 생각해봤다. 1. 출발지점(1)에서 도착지점(n)까지 도달하는 경로가 없을 때 -> -..

https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 백준 5014번 스타트링크를 풀었다. 이동하는 비용이 버튼을 누르는 횟수이므로 위로 가나 아래로 가나 비용이 똑같다. 그래서 BFS를 사용해서 풀었다. map[i] 배열에는 i번째 층까지 가는데 드는 최소 비용을 저장한다. visited[i] 배열은 i번째 층에 온 적이 있는지 확인하는 용도이다. 아래는 전체 코드입니다. #include #include #include using namespace std; #..

https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 백준 17472번 다리 만들기 2 를 풀었다. 문제에서 모든 섬을 연결하는 최소 비용을 구하라고 해서 최소 스패닝 트리로 풀어야 겠다고 생각했다. 문제를 풀기 전에 아래와 같이 생각하고 구현을 시작했다. 1. 섬에 번호를 매긴다. 2. 섬과 섬 사이에 놓을 수 있는 다리를 찾는다. 3. 크루스칼 알고리즘으로 최소 비용을 찾는다. 먼저 섬을 입력받은 후 섬마다 번호를 매겼다. ..

https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 백준 1937번 욕심쟁이 판다를 풀었다. 단순한 BFS/DFS 풀어보려 했는데 노드의 최대 개수인 250,000번을 수행해야 하므로 다른 방법을 사용해야 한다. 2차원 DP 배열과 DFS를 사용해서 풀었다. DP[i][j] 의 값은 판다가 (i, j) 좌표에 놓여졌을 때 살 수 있는 최대 일 수 이다. 어느 좌표에 놓이든 하루는 살 수 있으므로 DFS실행 시 해당 좌표의 DP값은 1로 ..

https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 백준 1167번 트리의 지름을 풀었다. 다익스트라를 두 번 사용해서 문제를 풀었다. 편의상 첫 번째 다익스트라는 1번 노드에서 시작하는 것으로 설정했다. 첫 번째 다익스트라를 실행하고 나면 1번 노드에서 가장 멀리 있는 노드를 리턴 값으로 넘겨주게 된다. 리턴되는 노드에서 다시 다익스트라를 실행하면 다시 그 노드로부터 가장 멀리 있는 노드를 넘겨준다. 넘겨준 노드와의 거리가 트리의..

https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 백준 9370번 미확인 도착지를 풀었다. 주어진 시작점에서 g->h 로 거쳐가거나 h->g 를 거쳐서 가는 루트가 도착 지점까지 최단 경로로 가는 루트인 도착 지점을 구하면 된다. s->g->h->d 또는 s->h->g->d 경로의 길이가 s->d인 경로의 길이와 같은 경우를 구하는 것이다. Dist배열을 3개 사용해서 다익스트라를 3번 수행했다. Dist_S[x] 의 값 = 시작점에서 x까..

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 백준 16234번 인구 이동을 풀었다. BFS에 구현을 섞은 문제인 것 같다. 1. N * N 좌표 상의 모든 점을 순회하면서 BFS를 돌린다. 2. 인구 이동이 일어났으면 변경된 map을 저장하고 1번으로, 인구 이동이 일어나지 않았으면 count를 출력하고 끝낸다. BFS를 돌릴 때 방문했던 점은 다시 방문하지 않는다. BFS코드에서 next좌표가 유효한 값일 때 cur좌표와의 ..

https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 백준 11052번 카드 구매하기를 풀었다. dp[i]의 값은 i개의 카드를 구매하는 최대 비용이다. 초기값은 dp[1] = cardpack[1] 이고, 반복문을 사용해서 dp[n]까지 구한다. 아래는 전체 코드입니다. #include #include #include #include #include #pragma warning(disable:4996) using namespace std; int n; in..

https://www.acmicpc.net/problem/10217 10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세 www.acmicpc.net 백준 10217번 KCM Travel 을 풀었다. 특정 노드에서 시작하고 간선의 가중치가 양수이므로 다익스트라를 사용했다. 변수가 비용과 시간 두개이므로 2차원 배열을 사용해서 풀어야 한다. dp[i][j] 는 시작 노드 1에서 i 노드까지 j 비용을 썼을 때의 소요시간을 저장하는 배열이다. https://maivve.tistory.com/226 위 블로그를 ..

https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 백준 10282번 해킹 문제를 풀었다. 의존성을 반대로 입력받은 뒤 감염된 컴퓨터에서 다익스트라 알고리즘을 사용하면 된다. 그러면 감염시킬 수 있는 컴퓨터의 개수와 걸리는 시간을 구할 수 있다. 출력과 초기화를 주의하자. 아래는 전체 코드입니다. #include #include #include #include #include #include #include #pragma warning(disable:..