뱀 문제 (0, 0) 에서 뱀이 오른쪽 방향을 보고 출발한다. n개의 명령 (이전 명령으로 부터 t시간 뒤에, dir 방향으로 머리를 돌림)을 수행하면서 격자판 밖으로 나가거나 자신의 몸에 부딪히는 시간을 구하는 문제이다. 문제 풀이 뱀이 지나온 칸들을 선분으로 저장해서 관리하기로 한다. 1. 초기에 테두리 선분 4개를 추가해준다. 2. 추가적으로 모든 명령이 끝난후 에도 선분에 부딪히지 않을수 도 있으므로 (inf,R) 명령을 하나 넣어준다. 3. 현재 (x,y)에서 dir 방향으로 이동할 때 현재 까지 저장된 선분들과 비교하여 최대로 이동할 수 있는 시간을 구한다. 4. 이 시간이 t보다 같거나 작으면 t시간을 이동하기 전에 선분들 중 하나에 부딪히는 것이므로 답을 출력한다. 5. 아니라면 t시간 만..
A. Bear and Big Brother 문제 Limak 와 Bob의 몸무게가 주어진다. Limak는 매년 3배씩 커지고 Bob은 2배씩 커진다. Limak가 Bob보다 커지기 위해서는 최소 몇 년이 지나야 하는지 구하는 문제이다. 문제 풀이 단순하게 1년 씩 늘리면서 2와 3을 각각 곱하고, Limak가 커질 때 출력하면 된다. 소스 코드 B. Bear and Friendship Condition 문제 친구 관계가 그래프로 주어진다. 한 컴포넌트내의 모든 정점이 서로 연결되어 있는지(완전 그래프)인지 판별하는 문제이다. 문제 풀이 각 정점마다 연결된 간선이 해당 정점이 포함된 컴포넌트 크기 - 1 인지 확인한다. 소스 코드 C. Bear and Different Names 문제 N명의 군인이 있고, ..
째로탈출 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값을 \(..
A. Anton and Polyhedrons 문제 다면체의 이름이 n개가 들어온다. 면들의 총합을 출력하면 되는 문제이다. 문제 풀이 각 다면체의 이름들의 첫 글자가 다르므로, 첫 글자만 비교하여 계산할 수 있다. 소스 코드 #include using namespace std; int n; char input[100]; int main(){ scanf("%d", &n); int ans=0; for(int i=0;ipriority priority) { NodePair splitted = split(root, node->key); node->setLeft(splitted.first); node->setRight(splitted.second); return node; } else if (root..