누가봐도 다익스트라같이 생긴 문제이고, 실제로 다익스트라를 빠삭하게 이해하고 있다면 해결할수 있는 문제였다. www.acmicpc.net/problem/1854 1854번: K번째 최단경로 찾기 첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이어지는 m개의 줄에 www.acmicpc.net 다익스트라는 탐색 도중에서 의도적으로 최단경로가 아닌 경우를 배제하는데, 이 배제되는 경로들을 전부 잘 저장해두고 정리해주면 된다. if(ans[next].size() < k){ pq.push({-(dist+dis), next}); ans[next..
제목이 같은 날먹문제... 트리에 존재하는 모든 경로 중 가장 긴것의 길이를 찾으라하고 있다. dfs로 풀었다. 일단 가장 긴 경로는 반드시 리프노드 - 리프노드 간 길이일 것이다. 리프노드가 아닌 노드가 긴 경로가 된다면 그 노드의 자식노드로 더 긴 경로가 있을수밖에 없기 때문이다 ( 가중치의 길이가 음수가 될 수 없다 ) 처음 생각한것은 1을 기준으로 가장 긴 경로 & 두번째로 긴 경로 를 찾는 것인데, 중복문제도 있고, 그림에서처럼 1을 지나지 않는 가장 긴 경로도 있기에 일단 루트노드에서 가장 긴 경로를 찾고, 그 경로에서 나온 리프노드를 시작점으로하는 가장 긴 경로를 찾아주었다. 루트노드에서 가장 긴 경로와 실제 가장 긴 경로가 1 ) 하나도 겹치지 않는다면 조건에 모순이 생기고, 2 ) 겹친다..
약간의 두뇌가 가미된 배낭문제 기본적인 구조는 12865번 평범한 배낭과 동일하다. www.acmicpc.net/problem/12920 12920번: 평범한 배낭 2 첫 번째 줄에 N, M (1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000) 이 빈칸을 구분으로 주어진다. N은 민호의 집에 있는 물건의 종류의 수이고 M은 민호가 들 수 있는 가방의 최대 무게다. 두 번째 줄부터 N개의 줄에 www.acmicpc.net 먼저 딱 보고 생각한 것은 O(KNM)인데, 이렇게 되면 당연하겠지만 TLE가 나온다. O(KNM)은 N개의 물건에 대해서 1~K갯수가 있을텐데, 각각의 개수를 모두 "K배 더 무겁고 K배 가치가 더 나가는 물건" 으로 바꿔주면 쉽게 나온다. AC는 O(NlogKM) 으로 받았는데, K를..
말 그대로 평범한 배낭 문제... www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 0/1 배낭 문제이다. dp[i][j] 를 i번째까지 살펴본 배낭의 용량이 j일때의 최대 가치 로 정의하면 풀수 있다. 이 최대 가치를 만드는법은 크게 세가지 경우로 나뉘는데 1) 배낭에 i번째를 넣을수 있고, 넣었음. ( dp[i][j] = dp[i-1][j-w[i]] + v[i] ) 2) 배낭에 i번째를 넣을..
의외로 골드V에 날먹이 많구만 아주 좋다. www.acmicpc.net/problem/17828 느낌표를 출력해야 하는 경우는 단 두가지밖에 없다. 1 ) ZZZZZZ와 같이 길이가 N일때의 가치를 최대로 해도 X에 미치지 못하는 경우 2 ) N일때의 가치를 최소로 해도 X보다 커지는 경우 각각 n*26 x 라는 수식을 통해 판별해줄 수 있다. 사전순으로 앞서는 문자열을 만들기위해서는 다른건 다 무시하더라도 앞에 오는 A의 개수가 가장 많아지면 될 것이다. 그렇기에 최대한 타이트한 선까지 A를 출력하고, A와 Z 사이에 "단 한글자만" 남는 가치를 매꾸고, 남은 모든 길이를 Z로 출력해주면 사전순으로 가장 앞서는 문자열이 만들어지게 된다. 더보기 #include using namespa..
www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 브루트포싱. 처음 보고 든 생각은 그냥 최대값까지 for문 돌리면서 감소하는 수들을 벡터에 담는 것이었는데, 이렇게 하자니 TLE가 나올것이 눈에 보여서 다른 방법으로 접근해보도록 했다. 가장 큰 감소하는 수는 9876543210일것이고, 가장 작은 감소하는 수는 0이 된다. 감소하는 수들의 특징은 수들의 정렬 순서가 내림차순으로 일정하다는 것인데, 확률과통계를 배우는 고딩들은 알겠지만 정렬 순서..
오늘 학원에서 써먹은 개념을 그대로 쓸수 있었던 문제 nHr 중복조합을 구현하면 되는 문제이다. 0
비트DP였다. 방문한 적이 있는 숫자들을 비트에 박아넣으면 된다. www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net dp[i][j][k] 를 현재 문자열 길이가 i이고, 지금 제일 앞 숫자가 j이고, chk 비트필드가 k일때로 뒀다. 더보기 #include #define MOD 1000000000 using namespace std; typedef long long ll; ll dp[123][12][19) return 0; if(len == n){ if(bit == (1
맞왜틀이 심했던 문제 vis배열을 초기화하자!! *복창중* www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 이상하리만치 MLE가 박혀서 결국 VIS배열 박았다... :thinking: #include using namespace std; queue q; int input,ans; int d1,d2,d3,d4; int k,t; string s; int vis[12345] = {0}; void bfs(){ while(!q.empty()){ k = q..
www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 보통 PQ두개 써서 구현하겠지만 나는 Multiset을 써서 구현해봤다 삽입은 O(logN), 삭제는 amortized O(1)에 동작하므로 충분히 AC를 받기에 적합한 시간복잡도이다. multiset::end()는 마지막 값보다 한칸 더 뒤에 있는 위치를 가리키므로 erase를 통해 지우려면 (--s.end())로 써줘야 정상적으로 지울 수 있다. 더보기 #include using namespace std..