주사위 굴리기 문제 지도 위에서 주어진 명령에 따라 주사위를 굴린다. 각 명령에 대해서 주사위 맨 윗면의 값을 출력하는 문제이다. 문제 풀이 시뮬레이션 문제이다. 명령이 K번 존재하므로 \(O(K)\)로 해결가능하다. 주어진 그림과 같이 항상 맨 윗면이 1 바닥과 닿아 있는 면을 6으로 생각하고 구현해보자. 오른쪽으로 구르는 경우를 예시로 들면 1. 먼저 구를수 있는지 판단(다음 좌표가 지도 내부인지) 2. 다음 주사위 상태에서 2번과 5번 면은 변하지 않는다. 오른쪽이므로, 현재 1번 면이 다음 3번 면으로 현재 4번 면이 다음 1번 면으로 현재 6번 면이 다음 4번 면으로 현재 3번 면이 다음 6번 면으로 바뀌게 된다. 3. 다음 상태공간을 만들었다면 6번 면과 지도 값을 비교하여 문제에 주어진 조건..
2048(Easy) 문제 게임의 규칙이 문제의 설명과 같을 때 최대 5번 움직여서 만들수 있는 최대 블록의 값을 구하는 문제이다. 문제 풀이 1. 깊이가 최대 5이고 하나의 상태공간에서 상하좌우 4개의 상태공간으로 전이 가능하다. 다음 상태공간을 만드는데 \(O(N^2)\)이 걸리므로, \(O(N^2 4^5)\) 로 해결 가능하다.2. 각 행(또는 열)에 대해 0이 아닌 블록들을 모은 후 2개씩 묶어서 합치는게 가능하면 합친다. 결과를 다시 해당 열에 복사한다.3. 구현 팁으로는 상, 하 // 좌, 우는 각각 순서만 반대로 넣으면 되고 세로와 가로는 행과 열만 바꾸어 넣으면 된다. ** 구현 실수하기 쉬운 예를 적어 보겠다.- 상, 하, 좌, 우를 따로 구현 하였는데 규칙이 다르게 구현 되어있음.- 2 ..
뱀 문제 (0, 0) 에서 뱀이 오른쪽 방향을 보고 출발한다. n개의 명령 (이전 명령으로 부터 t시간 뒤에, dir 방향으로 머리를 돌림)을 수행하면서 격자판 밖으로 나가거나 자신의 몸에 부딪히는 시간을 구하는 문제이다. 문제 풀이 뱀이 지나온 칸들을 선분으로 저장해서 관리하기로 한다. 1. 초기에 테두리 선분 4개를 추가해준다. 2. 추가적으로 모든 명령이 끝난후 에도 선분에 부딪히지 않을수 도 있으므로 (inf,R) 명령을 하나 넣어준다. 3. 현재 (x,y)에서 dir 방향으로 이동할 때 현재 까지 저장된 선분들과 비교하여 최대로 이동할 수 있는 시간을 구한다. 4. 이 시간이 t보다 같거나 작으면 t시간을 이동하기 전에 선분들 중 하나에 부딪히는 것이므로 답을 출력한다. 5. 아니라면 t시간 만..
째로탈출 2 문제 N*M 보드에 파란 구슬 빨간 구슬 구멍이 한 개씩 있고, 상하좌우 4방향으로 기울일 수 있을 때, 최소 몇 번 만에 빨간 구슬이 구멍에 나올 수 있는지 출력하는 문제이다. 단, 파란 구슬이 구멍으로 같이 나오면 실패이다. 문제 풀이 최대 10번 까지 보드를 조작할 수 있으므로, BFS 탐색을 이용하면 각 상태 공간에서 상하좌우 4방향으로 전이 가능 하고, 한 상태 공간에서 해당 방향으로 최대 \(max(N,M)\) 만큼 이동할 수 있으므로 \(O(4^{10} max(N,M))\) 임을 알 수 있다. 따라서 각 상태 공간 내에서 한 방향으로 이동 할 때1. 빨간 구슬과 파란 구슬이 일직선 상에 없음1.1) 빨간 구슬이 가는 길에 구멍이 있는 경우 --> 탈출 성공1.2) 파란 구슬이 가..
영화 수집 문제 쿼리마다 i 번째 영화 위에 쌓여있는 다른 영화의 수를 출력하는 문제이다. 문제 풀이 naive하게 쿼리마다 현재 영화보다 위에 있는 영화를 카운트하는 방식으로는 \(O(NM)\) 이라 불가능하고, 힌트로는 영화를 꺼냈을 때 그 부분이 밀쳐지지 않고 비워진다는 방식으로 이해한다는 것이다. 그리고 영화를 꺼내면 맨 위에 차곡차곡 쌓는다. 그래서 현재 i층에 영화가 존재하는지, 안 하는지를 저장하는 \(check[i]\)을 생각해 보자. index value 0 0 1 0 2 0 .... .. m 1 m+1 1 m+2 1 ... ... m+n-1 1 초기의 \(check[i]\)값은 위와 같다. 여기에 현재 i번째 영화가 어디 있는지에 대한 \(idx[i]\) 배열을 만들어 준다. 초기에는 ..
소문난 칠공주 문제 상하좌우로 연결된 크기가 7이고 S가 4 이상 포함된 컴포넌트의 개수를 세는 문제이다.개 문제 풀이 한 점을 기준으로 단순 bfs나 dfs로는 십자가 모양 등을 찾을 수가 없다. 따라서 25개의 학생 중에서 7명을 뽑고 여기서 S가 4 이상 포함되었는지 그리고 모두 연결되었는지를 판단하는 방식으로 구현하였다. \( \begin{pmatrix} 25 \\ 7 \end{pmatrix} = 480,700\) 이고 7명 중 한 명에서 dfs로 최대 컴포넌트 크기가 7인 경우만 가능한 경우로 판단하여 정답을 구하면 된다. \( O(480,700*25) \) 로 해결 가능하다. 소스 코드
운전 면허 시험 문제 (1,1)에서 (M,N)까지 이동하는데 남쪽과 동쪽으로만 이동할 수 있고 위 그림과 같이 이동하는데 길 상태에 따라 연료 g가 소모된다. 방향을 틀 때 1의 시간이 소모되고, 1개 변을 이동할 때 l 시간이 소모될 때 최대 가용 연료 G 이내로 들어올 수 있는 최소 시간을 구하는 문제이다. 문제 풀이 가장 쉽게 떠올릴 수 있는 풀이는 \(O(NMG)\) bfs 서칭 하는 방법이다. 물론 공간, 시간복잡도가 불가능한 풀이이고, 핵심적인 힌트는 이동하는데 걸리는 시간은 이동이 남쪽과 동쪽만 가능하므로 변의 개수는 의미가 없고 방향을 바꾼 횟수만 카운트해주면 된다는 점이다. 따라서 dp 테이블을 \(dp[x][y][k][dir]=(1,1)에서\: (x,y)좌표까지\: k번\: 방향을\: ..
풍선 맞추기 문제 N개의 풍선이 일렬로 놓여있고 화살을 쏴서 풍선을 맞추는 데 모든 풍선을 터트릴 수 있는 최소 화살의 개수를 구하는 문제이다. 화살은 처음 h 높이로 쐈다면 풍선 하나를 터트리면 h-1 높이로 바뀌어서 계속 날아간다. 화살은 왼쪽에서 오른쪽으로 쏜다. 문제 풀이 i번째 풍선을 직접 맞출지 다른 풍선을 거쳐서 맞추는지는 이 i번째 풍선 왼쪽으로 a[i]+1의 값을 가진 풍선을 맞췄는지 안 맞췄는지를 체크해주면 된다. 안 맞췄다면 i번째 풍선은 직접 화살을 쏴서 맞춰야 하는 풍선이므로 화살 개수를 ++해주면 된다. 아닌 경우는 a[i]+1의 값을 가진 풍선을 없는 것으로 바꾸고 a[i] 값의 풍선이 맞췄음을 갱신해주면 된다. 1차원 배열로 구현할 수 있다. 소스 코드 #include usi..
조세퍼스 문제 2 문제 조세퍼스 순열을 구하시오! (1 ≤ M ≤ N ≤ 100,000) 문제 풀이 naive 하게 \(O(NM)\)에 풀 수 있다. \(sum[i]=\sum_1^i{alive[x]},\:(alive[i]=i번째 \:사람이 \:살아있으면 \:1 \:아니면 \:0)\) 라고 정의 하자. 현재 i번째 사람부터 시작한다면 제거된 사람을 제외하고 \(sum[j]-sum[i]=m\)을 만족하는 j값을 찾으면 된다. m값이 현재 남아있는 사람보다 큰 경우와 j인덱스가 한 바퀴를 돌아 i보다 작은 경우 두 경우만 처리를 해주고 찾게 되면 여전히 \(O(NM)\)이다. 하지만 \(sum[i]\)는 순 증가함수고 근이 한 개만 존재하기 때문에 parametric search를 사용할 수 있고 j값을 \(..