두 개의 네비게이션 문제 그래프가 주어지고 1번 회사에서 N번 집까지 가는동안 경보음을 최소로 듣는 경우를 구하는 것이다. 문제 풀이 먼저 출발지인 회사에서 집으로 가는 경로 들은 여러곳이 있을 것이다.dist[x] 를 x에서 부터 n까지 가는 최단거리라고 정의하자.그렇다면 현재 위치 u와 연결된 v들에 대해서 dist[v]+w(u,v) == dist[u] 라면 v는 u에서 가는 최단 경로이다.아니라면 v로 가면 경보음이 울리게 된다. 이와 같은 정리를 이용해서 아이폰과 안드로이드를 사용하였을 때 u->v의 경보음이 울리는지울리지 않는지 판별하면 된다.모든 위치 u와 그와 연결된 v에 대해서 위의 값을 구하고 새로운 그래프를 만든후 다시 한번 최단경로 알고리즘을 돌리면 된다. 약간 디테일한 구현 방법으로..
그릇 모으기 문제 n개의 그릇 더미가 있다 각 그릇 더미는 최대 h개의 그릇이 쌓여있고 항상 큰 그릇 위에 작은 그릇을 놓을 때 주어진 연산들을 사용하여 한 개의 그릇 더미로 만드는 최소 연산 횟수를 구하는 문제이다. 문제 풀이 문제를 좀 더 단순화하여 약한 조건으로 생각해보자.0번 그릇 더미를 새로 만들고 여기에 우리가 최후의 더미를 만든다는 조건과,모든 그릇의 크기는 각각 다르다는 조건을 추가해보면 우리는 주어진 접시들을 소팅한 후 가장 큰 접시부터 0번 그릇 더미위에 올리면 된다.따라서 현재 크기의 접시를 0번 그릇 더미 위에 올리는데 드는 연산 횟수는 다음과 같다.먼저 현재 크기의 접시를 해당 그릇 더미 맨 아래 (그보다 큰 접시는 이미 0번 그릇 더미로 옮겨 졌기 때문에) 에서 분리하기 위해서는..
주사위 굴리기 문제 지도 위에서 주어진 명령에 따라 주사위를 굴린다. 각 명령에 대해서 주사위 맨 윗면의 값을 출력하는 문제이다. 문제 풀이 시뮬레이션 문제이다. 명령이 K번 존재하므로 \(O(K)\)로 해결가능하다. 주어진 그림과 같이 항상 맨 윗면이 1 바닥과 닿아 있는 면을 6으로 생각하고 구현해보자. 오른쪽으로 구르는 경우를 예시로 들면 1. 먼저 구를수 있는지 판단(다음 좌표가 지도 내부인지) 2. 다음 주사위 상태에서 2번과 5번 면은 변하지 않는다. 오른쪽이므로, 현재 1번 면이 다음 3번 면으로 현재 4번 면이 다음 1번 면으로 현재 6번 면이 다음 4번 면으로 현재 3번 면이 다음 6번 면으로 바뀌게 된다. 3. 다음 상태공간을 만들었다면 6번 면과 지도 값을 비교하여 문제에 주어진 조건..
새로운 방 문제 (1,1)에서 (n,n)으로 최단거리로 이동하고, 만나는 방의 모든 돈을 곱해서 6진수로 변환할 때 뒤에서 부터 연속된 0의 갯수의 최대값을 구하는 문제이다. 문제 풀이 최단 거리로 이동하므로, 아래 또는 오른쪽으로만 이동 가능하다. 따라서 동적계획법을 적용할 수 있고, 결국 (n,n) 방에 도착 하고 소인수 분해 하였을 때 min(2의 개수, 3의 개수) 의 최대값을 구하는 문제로 바뀐다. 한 방에 3은 최대 6개 들어 갈수 있고 (n,n) 에서 최대 6만개 까지 존재 할수 있으므로 \(O(N^2 * 60000)\) 으로 해결 가능하다.\( dp[i][j][k]=\: i\: 행\: j\: 열에서\: 현재\: 까지\: 모은\: 3이\: k\: 개\: 일\: 때\: 최대로\: 모을\: 수있..
A. Anastasia and pebbles 문제 Anastasia 에게 2개의 주머니가 있고 각 주머니에 최대 k개의 조약돌을 넣을 수 있다. 또한 한 주머니에는 한 종류의 조약돌만 넣을 수 있을 때 모든 조약돌을 줍는데 걸리는 최소 일자를 구하는 문제이다. 문제 풀이 매일 각 주머니에 최대한 넣는걸 반복하면 된다. 소스 코드 B. Masha and geometric depression 문제 b, q, l, m 이 주어졌을 때 보드에 적게되는 수열의 수를 구하는 문제이다. 문제 풀이 b가 0인 경우와 q가 -1, 0, 1 인 경우들을 잘 분리해서 구현하면 된다.좀 더 생각해보면 q가 -1인 경우만 제외해서 구현하면 쉽게 구현할 수 있다.싸이클을 체크하는 use set와 bad integer를 저장하는 ..
2048(Easy) 문제 게임의 규칙이 문제의 설명과 같을 때 최대 5번 움직여서 만들수 있는 최대 블록의 값을 구하는 문제이다. 문제 풀이 1. 깊이가 최대 5이고 하나의 상태공간에서 상하좌우 4개의 상태공간으로 전이 가능하다. 다음 상태공간을 만드는데 \(O(N^2)\)이 걸리므로, \(O(N^2 4^5)\) 로 해결 가능하다.2. 각 행(또는 열)에 대해 0이 아닌 블록들을 모은 후 2개씩 묶어서 합치는게 가능하면 합친다. 결과를 다시 해당 열에 복사한다.3. 구현 팁으로는 상, 하 // 좌, 우는 각각 순서만 반대로 넣으면 되고 세로와 가로는 행과 열만 바꾸어 넣으면 된다. ** 구현 실수하기 쉬운 예를 적어 보겠다.- 상, 하, 좌, 우를 따로 구현 하였는데 규칙이 다르게 구현 되어있음.- 2 ..