문제링크 : https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net #include using namespace std; #define ll long long #define MAX 987654321 #define pii pair int N, M, K, X; //도시 갯수, 도로 갯수, 거리 정보, 출발 도시 번호 int dist[300001]; vectorv[300001]; ve..
문제링크 : https://www.acmicpc.net/problem/13398 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net #include using namespace std; #define ll long long #define MAX 987654321 #define pii pair int arr[100001]; int dp[100001][2]; //제거하지 않은 경우와 제거한 경우 int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int N, re..
문제링크 : https://www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net #include using namespace std; #define ll long long #define MAX 987654321 #define pii pair ll arr[1000]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int N, M; cin >> N >> M; for(..
문제링크 : https://www.acmicpc.net/problem/2513 2513번: 통학버스 첫째 줄에는 세 개의 양의 정수 N, K, S가 빈칸을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 아파트 단지의 수이며 2 ≤ N ≤ 30,000이다. 두 번째 정수 K는 1 ≤ K ≤ 2,000이며, 통학버스의 정원 www.acmicpc.net #include using namespace std; #define ll long long #define MAX 987654321 #define pii pair int N, K, S; //단지 수, 통학버스 정원, 학교 위치 vector lefts; vector rights; int distance(vector v) { int pos = S, num = ..
문제링크 : https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net #include using namespace std; #define ll long long #define MAX 987654321 #define pii pair pair tree[26]; void pre(char node) //전위 { if(node == '.') return; cout > root >> left >> right; tree[root - 'A'].first =..
문제링크 : https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net #include using namespace std; #define ll long long #define MAX 987654321 #define pii pair int R, C, T, result = 0; int arr[50][50]; //기존 배열 int arr_changed[50][50]; //변동된 배열 int dr[] = {1, -1, 0, 0}; int dc[] = {0, ..
문제링크 : https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net #include using namespace std; #define ll long long #define MAX 987654321 #define pii pair int N, M, K; int parent[51]; //진실을 아는 사람의 수 vectorknow; vectorparty[50]; //파티 오는 사람 수 int find_root(int x) { if(x == parent[x]) retu..
문제링크 : https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net #include using namespace std; #define ll long long #define MAX 987654321 #define pii pair int dp[2][100001]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int T, N; cin >> T; while(T--) { cin >>..
문제링크 : https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net #include using namespace std; #define ll long long #define MAX 987654321 #define pii pair struct Info { int s, e, t; }; int N, M, W; int dist[501]; vectorv; void Bellman_Ford() { for(int i=1; i 음수사이클 존재 { cout..
문제링크 : https://www.acmicpc.net/problem/1817 1817번: 짐 챙기는 숌 첫째 줄에 책의 개수 N과 박스에 넣을 수 있는 최대 무게 M이 주어진다. N은 0보다 크거나 같고 50보다 작거나 같은 정수이고, M은 1,000보다 작거나 같은 자연수이다. N이 0보다 큰 경우 둘째 줄에 책 www.acmicpc.net #include using namespace std; #define ll long long #define MAX 987654321 #define pii pair int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int N, M; cin >> N >> M; int tmp = M; int weight, cn..
문제링크 : https://www.acmicpc.net/problem/12996 12996번: Acka 첫째 줄에 앨범에 포함된 곡의 개수 S와 dotorya, kesakiyo, hongjun7이 불러야 하는 곡의 수가 주어진다. (1 ≤ S ≤ 50, 1 ≤ dotorya, kesakiyo, hongjun7 ≤ S) www.acmicpc.net #include using namespace std; #define ll long long #define MAX 987654321 #define pii pair #define MOD 1000000007 int S, s1, s2, s3; ll dp[51][51][51][51]; ll func(int S, int s1, int s2, int s3) { if (s1 ..
문제링크 : https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net #include using namespace std; #define ll long long #define MAX 987654321 #define pii pair int A, B; int D, S, L, R; bool visited[10000]; void bfs() { queue q; q.push({A, ""}); visited[A] = 1; while(!q.empty())..
문제링크 : https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net #include using namespace std; #define ll long long #define MAX 987654321 #define pii pair int N; int arr[20][20]; int dx[] = {1, -1, 0, 0}; int dy[] = {0, 0, 1, -1}; struct Info { int y, x, dist; }; struct Cmp{ b..
문제링크 : https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net #include using namespace std; #define ll long long #define MAX 987654321 #define pii pair int V, E; int start; int u,v,w; int arr[200001]; //정점 vectoredge[300001]; //간선+가중치 void dijkstra() { arr[..