본문 바로가기

반응형

알고리즘

3421. 수제 버거 장인 3421. 수제 버거 장인 처음에 시간초과가 발생할 것 같아서 어떤 방식으로 풀지 굉장히 고민했다. if(burger[state])==1){return ;} 이 부분만으로 통과가 될 수 있을까 했는데 다행히 시간초과에서 벗어났다. 비트마스크를 다시 한번 사용해볼 수 있었던 문제. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960#include#includeusing namespace std;int N, M;int burger[(1 a >> b; k = (1 더보기
4206. 연구소 탈출 4206. 연구소 탈출 이전에 백준에서 비슷한 문제를 풀어본 적 있었던 것 같다. 예전에 백준에서 내가 풀 때는 맵을 두개를 만들고, 서로 비교하면서 문제를 풀었는데 풀고나서 다른 사람들 풀이를 보다가 BFS를 서로 번갈아가면서 풀었던 코드를 봤던게 생각났다. 이 문제도 마찬가지로 사람이 움직이고, 바이러스를 움직이면서 탈출 여부를 판단하면 된다. 사람이 맵의 끝자리에 있으면 탈출할 수 있다. (단, 그 자리가 탈출하기 직전에 바이러스에게 먹히면 안된다.) 바이러스에게 먹히면 안되는 것을 간과해서 문제를 틀렸었다. 그리고 탈출하지 못하면, 전체 맵을 탐색하면서 사람이 남아있는지를 파악한다. (맵에 3의 존재 여부) 3이 존재한다면, 좀비는 되지 않았지만 탈출할 수 없는 구조이기 때문에 CANNOT ESC.. 더보기
4193. 수영대회 결승전 4193. 수영대회 결승전 기존의 BFS 문제에서 조금 달라졌다. 소용돌이가 생겼다 없어졌다 하는 주기가 반복되는 문제였다. 소용돌이가 없어져서 소용돌이 속으로 움직일 수 있는 시간이 3초,6초,9초.. 이런식으로 반복된다. 따라서 다익스트라를 이용해서 가중치를 주는 방식으로 문제를 풀었다. 단 소용돌이 이전 단계에서 현재 dist 값을 3가지로 나눠서 문제를 풀었다. dist%3==0 , dist%3==1, dist%3==2 인 경우로 나누었다. 예를 들어 0초인 경우에는 dist%3==0 이기 때문에 소용돌이로 이동하기 위해선 3초를 기다려야 한다. 따라서 움직이면 3을 추가한다. 1초인 경우에는 dist%3==1 이고, 소용돌이로 이동하기 위해서는 2초만 기다리면 된다. 이런식으로 케이스를 나누어서.. 더보기
3977. 페르마의 크리스마스 정리 3977. 페르마의 크리스마스 정리 처음 문제를 보고는 그냥 에라토스테네스의 체를 이용해서 문제를 푸는구나 했다. 에라토스테네스의 체를 미리 한번만 구하도록 했는데, 시간초과가 발생했다. 그래서 아! DP문제로 다시 풀 수 있겠구나하고 제출했는데.. 정답이 계속 틀렸다.. 분명 코드는 맞는거 같은데 그러다가 문제의 댓글에 나와 똑같은 분을 봤는데.. 예외적으로 2라는 값은 4로 나누었을 때 1이 아니지만, 1^2 + 1^2 이므로 정답에 해당했다..! 아주 큰 예외를 생각하지 못하고 있었다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859#include#in.. 더보기
1249.보급로 1249. 보급로 다익스트라를 이용해서 시작점에서 끝점까지 최단거리를 구하면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364#include#includeusing namespace std;const int INF = 987654321;int dx[4] = { 0,0,1,-1 };int dy[4] = { 1,-1,0,0 };int main(){ //freopen("input.txt", "r", stdin); int tc; cin >> tc; for (int t = 1; t > n; for (int i = 0; i= 0 && nx 더보기
2814. 최장 경로 2814. 최장 경로 쉬운 문제라고 생각했는데, 결국 다른 사람의 힌트를 보고 나서야 풀 수 있었다..ㅠㅠ 그냥 단순히 각 정점을 돌면서 DFS를 돌리면 될거라고 생각했다.. 하지만 만약 사이클이 생긴다면, 최장 거리가 달라질 수 있기 때문에 DFS에서 return 하기 전에 방문한 지점의 방문표시를 해제해줘야 했다.. 생각이 짧아도 너무 짧았다.. 아래 그림에서 1->2->3->4->5 까지 방문을 먼저하고 3->7->6 이 되는 경우 최장거리는 5밖에 되지 않는다. 하지만 return 하면서 방문체크를 해제한다면 1->2->6->7->3->4->5 가 되기 때문에 최장거리가 7이 된다. 1234567891011121314151617181920212223242526272829303132333435363.. 더보기
4112. 이상한 피라미드 탐험 4112. 이상한 피라미드 탐험 BFS 문제였기 때문에, 각 노드간에 이동할 수 있는지 여부만 추려내면 되는 문제였다. 근데 나는 딱히 방법이 떠오르지 않아서 약간 노가다 식으로 진행했다. 일단 1인경우, 맨 왼쪽 대각선인 경우, 맨 오른쪽 대각선이 경우, 그외 이렇게 나누어서 문제를 풀었다. 중복계산을 피하기 위해 tc안에 들어가기 전에, 각 숫자들을 for문으로 돌면서 해당하는 라인과 왼쪽인지 오른쪽인지를 판단하도록 했다. 이때 1은 왼쪽,오른쪽 둘다 걸쳐 있다고 체크를 해줬다. 그리고 BFS를 돌면서, 다음 정점을 찾을 때는 1인지,왼쪽대각선인지,오른쪽대각선인지, 그 외 경우인지 나누어서 함수를 진행했다. 그리고 사실 이동할 때 1이상 1만이하인지를 체크해줘야 하는데 귀찮아서 배열을 아주 크게 만들.. 더보기
4111. 무선 단속 카메라 4111. 무선 단속 카메라 거리의 모든 합은 결국 정해져 있기 때문에, 가장 큰 값부터 없애나가면 된다고 생각했다. 즉 예제에서 1-3-6-7-9 에 카메라가 있다면, 그 사이의 거리는 2-3-1-2 가 된다. 이때 k값이 2라면, 2 3 1 2 중에서 3만을 제거하면 구간이 두개가 되고 2 , 1-2 가 되어 합 5가 정답이 된다. 이런식으로 정렬해서 k의 값에 따라 가장 큰 값을 차례로 제거해주면 된다. 따라서 1. 카메라가 있는 곳의 위치를 파악한다. 2. 중복 계산을 피하기 위해 다시 카메라의 위치를 통합하여 v 벡터에 담는다. 3. v벡터를 이용해서 카메라 사이의 거리 값을 모두 diff 벡터에 담는다. 4.diff를 정렬하여 k값에 따라 앞에서부터 더해간다 //배운점 처음에 size선언을 하.. 더보기

반응형