다익스트라를 복습하기 위해서 문제를 풀어보았다.  사실 이렇게 해서 풀릴 줄 몰랐는데그냥 다익스트라를 여러 번 돌려서 해결되었다. 정점 2개를 무조건 지나가야 하기 때문에시작 지점, 정점1, 정점2에서 다익스트라를 이용해 한 번씩 돌려 거리 값을 구하고최소 거리를 계산하는 방식으로 해결했다.#include #include #include #include using namespace std;int INF = 98765432;long NodeDist[801];vector> Nodes[801];int N, E;void BFS(int start){ memset(NodeDist, INF, sizeof(NodeDist)); NodeDist[start] = 0; queue q; q.push(start); while..

https://www.acmicpc.net/problem/1101풀이 상자에 카드를 옮겨야하는 경우의 수를 체크해 조커 상자에 다 갖다 넣으면 된다.하지만 조건 3번을 보면 같은 색을 가진 모든 카드는 모두 같은 박스에 있어야하기 때문에 이미 그 색의 카드를 정리한 상자가 있는 경우에는 옮겨야한다. 1. 상자가 비어있는 경우2. 상자에 있는 카드의 색이 1종류만 있는 경우+ 그 색의 카드를 정리한 상자가 없는 경우를 제외하고 나머지 경우에는 옮겨주는 수를 센다. 이러한 방식으로모든 박스가 조커 박스인 경우를 하나씩 계산하여 최소값을 구하면 된다.  개인적으로 어려웠던 부분문제는 굉장히 쉬운데, 이해 과정에서 어려움을 겪었다.0은 비어있는 것이고, 군데 군데 적혀있는 숫자들이 컬러값인 줄 알았는데,알고보니..

백트래킹 복습할 겸 문제를 풀어보았다. 시간 초과로 인해 계속 수정하느라 원래 코드와는 일부분 바뀌긴 했으나시간 초과가 났던 이유는 이 부분 때문이었다. i = 0 부터 시작하면 시간초과가 난다.당연한 부분인데 당연히 i = idx라고 적어놓은 줄 알고 30분을 날렸다. ㅎ.ㅎ #include #include #include #include using namespace std;vector vec;bool visited[26];int answer = 0;int N, K;int CanReadNum(){ int value = 0; for (int i = 0; i > N >> K; string inputStr; for (int i = 0; i > inputStr; vec.push_back(inputStr.su..

https://www.acmicpc.net/submit/1149/77958078 DP 복습 겸 한 번 풀어보았다.struct를 써서 풀어보고 싶어서 이런 식으로 코드를 짰는데, 구조나 속도면에서 좋은지는 잘 모르겠다.#include #include #include using namespace std;struct RGB{public: RGB() : R(0), G(0), B(0) { } RGB(int r, int g, int b) : R(r), G(g), B(b) {}public: int R; int G; int B;};int hCount;vector hColorCostInfos;int DP[3][1001];// 색, 몇 번째 집int main(){ cin >> hCount; for (int i = 0; i..

https://www.acmicpc.net/problem/1167https://www.acmicpc.net/problem/1967 1167 문제를 풀었는데, 1967 또한 똑같은 코드에서 살짝 수정해서 해결이 되는 문제이다. 1167 코드#include #include #include using namespace std;vector> vertexInfos[100001];// vertexNum, lengthint vertexSize = 0;int maxVertex = 0;unsigned long long answer = 0;bool visited[100001];int DP[100001];void InputVertexInfo();void DFS(int vertexNum, int dist){ if (visit..

문제_링크 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 일단 문제를 이해해보자. 이렇게 입력이 된 테스트 케이스에서 답이 3이 나오게 된다. 일단 c와 z 열쇠를 가지고 시작한다. c열쇠로 C문을 열고 들어가서 p열쇠를 얻을 수 있다. p열쇠로 P문을 열고 들어가서 a열쇠를 얻을 수 있다. a열쇠로 A문을 열고 들어가서 x열쇠를 얻을 수 있다. x열쇠로 X문을 열고 들어가서 문서 하나를 획득할 수 있다. 오른쪽에 뚤려있는 공간으로 들어가서 X문을 열고 문서 두개를 획득할 수 있다. 이런 식으로 진행되는 것을 보고 BF..