계단을 오르듯이

플로이드-와샬 알고리즘을 이용해야한다. 플로이드 와샬 알고리즘은 O(n^3)의 시간복잡도를 가지며, 모든 정점의 이동거리를 구할 수 있다. 총 n개의 정점이 있다면 1개의 노드가 n-1의 노드까지의 연결 거리를 모두 알 수 있다. 우선 플로이드-와샬 알고리즘을 통해 서로의 연결 상태(간선의 개수)를 알 수 있고, 간선의 개수만큼의 시간이 걸린다. 현재 문제에서는 왕복의 거리이므로 간선의 수 한개당 2의 시간이 걸린다고 생각하고 시간 배열을 채웠다. 그 후, 치킨집을 조합으로 하여 모든 경우의 수를 통해 최소의 거리시간을 구하였다. 우선 2개의 치킨집을 조합으로 구한 후 모든 정점에서 2개의 치킨집 중 가장 가까운 치킨집을 구하여 그 시간을 모든 총 시간을 나타내는 시간에 더해주었고, 이렇게 모든 경우를 ..

길을 배열에 나타내는 것이 문제였다. 역시 어떻게 해야하나... 하면 언제나 풀이는 3차원 배열을 사용하는 것!!!! 길 역시 4개의 방향을 가지고 있기에 2차원으로 배열의 위치를 나타내고 +1차원을 추가해 3차원에서 4방향을 나타내도록 하여 해당 위치에서 상하좌우의 길 유무를 나타내도록 하였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 ..

처음 문제를 읽는데 문제 이해가 헷갈렸다. 문제를 해석하면 컨베이어 벨트는 시계 방향으로 원을 그리며 회전한다. 컨베이어 벨트가 회전할 때 위에 있는 로봇은 같이 움직이고, 벨트가 움직인 후 다시 로봇이 오른쪽으로 조건에 맞게 이동이 가능하다!! 그 후, 로봇이 올라가는 위치에서 올라갈 수 있다. 처음부터 로봇이 올라가는 것이 아니라 1단계에서는 로봇이 없는 채로 1번부터 4번까지 진행을 한다. 즉, 1,2번 진행 후 첫 로봇이 3번째에 올라가게 되는 것이다. 위의 문제에서 제시된 과정을 순서대로 작성하고 실행하면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 3..

규칙을 찾아보면 1부터 N까지일 경우 순서대로 홀수는 계속해서 버려지고 짝수는 뒤로 간다. 이 규칙을 찾아 for문을 돌렸고, 큐를 만들어 짝수는 큐에 넣어주었다. 그 후 while문을 통해 버림과 뒤에 겹침의 연산을 처리했고, while문의 연산은 짝수를 기준으로 하였으므로, 홀수에서는 무조건 while문을 들어가기 전에 한번 뒤로 붙임 처리를 해주어야 한다. while문 안에서도 연산 중 1개의 카드만 남게될 시 while문을 종료하고 그 카드를 출력해주어야 한다. 또한, N이 1일 경우는 위의 연산이 필요하지 않고, 무조건 1개의 카드가 존재하므로 바로 1을 리턴해주었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27..

가장 최소가 될 수 있는 값만 방문처리를 통해 구하면 성공할 것 같지만, 성공할 수 없다. 그 이유는 방문처리와 함께 가능한 최소의 값만을 구하는 것이 절대 최소가 될 수 없기 때문이다. 이유는 첫번째 최소의 값으로 방문처리를 하면 그 위치와 겹치는 곳을 제외한 곳에서 최소를 찾게 되기 때문이다. 그렇게 되면 한곳은 최소가 될 수 있지만 그 곳의 최소만을 보고 나머지를 생각하게 되면 나머지는 최대가 될 수도 있기 때문이다. 만약 첫번째 최소가 1이고, 그 곳을 제외한 곳의 최소가 99 라면 합은 100이다. 이 문제는 전체의 값을 최소가 되기 위함이므로 모든 경우를 고려해 적용해보는 완전탐색이 필요했다. 즉, 한곳에서는 최소가 아닌 값을 골라도 전체의 값이 최소가 될 수 있게 만들어야 한다. 그렇게 되면..

해당 폭탄이 터지기 전에 1초의 간격으로 모든 곳에 폭탄을 설치할 시간이 주어진다. 현재 시작을 1초로 하므로, 짝수의 시간에는 모든 곳에 폭탄이 설치된 배열이 정답이 된다. 홀수일 경우, 이제 계산을 해야주어야 하는데 이중 for문을 이용했다. 순서대로 배열의 값을 확인해 폭탄의 위치가 아닐 시 폭탄으로 바꿔주고, 폭탄일 시 폭탄의 연산을 해준다. 여기서 이미 폭탄의 영향으로 바뀌어진 부분을 다시 바꾸어줄 수 있는 영향이 존재하므로 방문처리를 해주었다. 폭탄의 연산에서는 방문처리에 상관없이 폭탄의 연산을 해주었고, 전체 폭탄은 동시에 터지는 것을 원칙으로 하기에 4방향으로 폭발할 때의 계산을 하기 전 그 위치가 다음 연산에 영향을 주는 오른쪽과 아래의 위치가 되어질 때는 그 부분을 if문을 통해 제외하..

우선 예산을 오름차순 정렬을 하여 제시된 총액으로 정해진 처음 상한가를 기준으로 연산을 시작한다. 상한액보다 작을 경우 다른 곳에 나누어 줄 수 있는 돈이 더 생기게 되는 것이므로 그 돈을 활용해 다시 상한액을 측정하였다. 모든 경우에서 상한가보다 낮을 경우가 있을 수 있기 때문에 상한가보다 낮을 경우 출력해야할 결과값인 최대 예산을 계속 갱신해주었다. 그 뒤 상한가보다 높은 가격의 예산이 나오게 되면 위에서 정렬을 이미 했기 때문에 그 뒤로부터는 계속해서 상한가보다 높은 예산이 나오게 되므로 예산의 가격이 아닌 한정가와 현재까지 최대값 예산과의 max비교를 통해 결과값을 갱신한 후 더이상의 연산은 모두 한정가와 같으므로 for문을 break 빠져나오게 했다. package november.second;..

평소처럼 dfs/bfs로 풀었지만 시.간.초.과.. 500 * 500 이라서 될 줄 알았지만, 모든 인덱스 위치에서 모든 경우를 다 계산해야 하기에 최대 500 * 500마다 500 * 500이 될 수 있으므로 250000 * 250000 가 되어 시간초과가 당연히 발생되는 것이다. 시간을 줄이고자 방문해서 도착지점에 도착했던 경로는 당연히 나중에도 그 길을 통해 도착이 보장되므로 그 길을 다시 확인하는 수를 줄여야겠다고 생각했다. dfs의 return값을 통해 방문과 함께 갈 수 있는 길의 수를 구하기 위해 dp와 dfs를 함께 이용해 풀었다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647pack..