소문난 칠공주 문제 상하좌우로 연결된 크기가 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..