본문 바로가기

Problem Solving/문제풀이

 (89)
백준 20925번 메이플스토리 문제 요약 사냥터가 N개 주어진다. 각 사냥터에는 사냥터에 진입하기 위한 최소 경험치 $c_i$와 1분마다 얻는 경험치 $e_i$가 주어진다. 그리고 각 사냥터 간 이동에 필요한 시간도 주어진다. 총 $T$분을 쓸 수 있다고 할 때, 얻을 수 있는 최대경험치를 출력하시오. 사냥터의 개수 N은 최대 200이고, $T$는 최대 1000이다. 풀이 이리저리 생각해볼 수도 있지만 일단 dp를 생각하자. $$ dp[i][j]=\text{i번째 사냥터에서 j분에 얻을 수 있는 최대 경험치}dp[i][j]=\text{i번째 사냥터에서 j분에 얻을 수 있는 최대 경험ㅊ} $$ 이러면 이제 j분에 i번째 사냥터에 있을 때 할 수 있는 선택은 두 종류가 있다. 이 사냥터에서 계속 사냥하거나, 다른 사냥터로 이동하거나. 이..
백준 20924번 트리의 기둥과 가지 문제 요약 트리와 루트노드가 주어진다. 처음으로 자식의 수가 2 이상이 되는 노드를 기가 노드라고 하자. 만약에 그런 노드가 없다면 리프 노드를 기가 노드라고 하자. 문제에서 원하는 것은 루트에서 기가 노드까지의 거리와 기가 노드를 루트로 하는 서브트리에서 기가 노드와의 거리가 가장 먼 노드의 거리를 출력해야 한다. 노드 수 N은 최대 20만이다. 풀이 먼저 기가 노드를 찾아야 한다. 이는 루트 노드에서 부터 dfs를 진행하면서 자식의 수가 2 이상인 노드를 찾으면 dfs를 종료하는 식으로 찾을 수 있다. 기가 노드에서부터 가장 먼 노드를 찾는 것도 위 과정에서 기가 노드의 부모만 잘 저장해뒀다가 dfs를 돌리면 찾을 수 있다. #include using namespace std; const int MA..
백준 20923번 숫자 할리갈리 문제 요약 플레이어가 두 명 있다. 각 플레이어의 카드 더미가 주어진다. 각 플레이어는 번갈아 가면서 본인의 그라운드에 본인의 카드 더미 제일 위에서 카드를 내려놓는다. 카드를 내려놓을 때 이미 그라운드에 카드가 놓여있었다면 이미 놓여있던 카드는 고려하지 않는다. 도중에 특정 조건을 만족하면 그라운드에 있는 카드들을 본인 카드 더미로 들고간다. 도도의 조건은 그라운드에 나와 있는 두 카드 중에 숫자가 5인 카드가 있는 것이고, 수연이의 조건은 그라운드의 나와있는 두 숫자의 합이 5가 되는 것이다. 단 비어있는 그라운드가 있어선 안된다. 도도가 먼저 이 과정을 시작한다. 한 사람이 승리하면 그라운드에 있는 카드들을 본인의 카드 더미 아래에 놓는다. 이런 과정을 반복할 때, 본인의 카드더미가 비게 되면 진다..
백준 20922번 겹치는 건 싫어 문제 요약 길이 $N$인 수열 $a$와 $K$가 주어진다. 연속 부분수열 중에서 같은 정수가 $K$개 이하로 포함되는 최장 연속 부분 수열의 길이를 출력하시오. N은 최대 20만, K는 최대 100, 주어지는 수들의 범위는 1부터 10만까지이다. 풀이 연속 부분 수열이기 때문에 투포인터를 사용할 수 있다. 현재 보고 있는 수열의 범위를 $[s,e)$라고 하자. 만약 e번째 수의 등장횟수가 이미 K번이라면 s를 오른쪽으로 옮기면서 현재 보고 있는 부분 수열의 길이를 줄여나간다. 그러다가 e번째 수의 등장횟수가 K보자 작아졌다면 s를 오른쪽으로 옮기는 것을 그만두고 다시 e를 늘련간다. 이렇게 하면 답을 찾을 수 있다. #include using namespace std; int N, K; int cnt[1..
백준 20921번 그렇고 그런 사이 문제 요약 정수 N, K가 주어진다. 1부터 N까지를 한 번씩 사용해서 inversion이 정확히 K개인 배열을 출력하시오. 여기서 inversion이란 배열을 $a$라고 했을 때, $ia_j$인 $(i,j)$를 말한다. 이러한 $(i,j)$가 $K$개인 배열 $a$를 출력하자. N은 최대 4242고 K는 0부터 $N(N-1)/2$이다. 풀이 일단 문제불가능한 경우는 없다고 제시했다. 그래고 한 번 왜 가능한지 생각해보자. $a_i$가 만들 수 있는 inversion의 수는 N-i개이다. 이를 통해 0부터 N-1까지를 사용해서 그 합을 K로 만드는 것과 같다고 생각할 수 있다. K가 0부터 N-1 사이일 때는 숫자 하나만 사용하면 된다. N부터 2N-3까지는 N-1하나랑 남은 수 중에서 하나를 선택하고,..
백준 20920번 영단어 암기는 괴로워 문제 요약 문자열이 N개가 주어진다. 문자열 중에서 길이 M보다 작은 문자열은 무시한다. 이 문자열들을 아래와 같은 기준으로 정렬해서 출력하시오. 등장 빈도 수가 더 많은 문자열을 앞에 배치한다. 등장 빈도 수가 같다면 길이가 긴 문자열을 앞에 배치한다. 빈도 수도 같고 길이도 같다면 사전 순으로 앞선 문자열을 앞에 배치한다. N은 최대 10만이고, M은 최대 10이다. 주어지는 문자열들은 길이 10으넘지 않는다. 풀이 문자열을 입력 받으면서 길이가 M 이상인 문자열들만 map을 이용해서 빈도수를 저장하자. 각 문자열들을 한 번씩만 등장하게 벡터에 저장하고 이 벡터를 주어진 조건에 따라서 정렬하면 된다. 정렬 기준은 함수나 람다 함수를 이용하면 편하다. 지금 보니까 944ms로 아슬아슬하다... #inc..
백준 7149번 Can of Worms 문제 요약 직선 상에 캔이 n개 놓여있다. 캔은 터질 수 있다. 각 캔이 놓여있는 위치 $x_i$와 캔이 터지는 반경 $r_i$가 주어진다. 캔이 터질 때, 터지는 반경 내에 있는 캔은 모두 연쇄적으로 터지게 된다. j번째 캔이 i번째 캔의 반경 내에 있으면 j번째 캔도 터지고 j번째 지뢰의 반경 내에 있는 캔은 모두 같이 터진다. 이 때, $i$번째 캔이 터졌을 때 같이 터지게 되는 캔의 수를 모두 출력하라. $n \le 10^9$, $1 \le x_i, r_i \le 10^9$이다. 풀이 이 문제를 그래프로 생각해보자. 그러면, $i$번째 캔의 반경 내에 존재하는 모든 캔들에 대해서 간선을 연결해주자. 그렇게 만든 그래프에서 DFS를 돌리면 문제가 해결이 가능하다. 그러나, 간선 수가 $O(N^2)$..
백준 1892번 가위바위보 문제 요약 두 사람이 가위바위보를 하는데 총 N번까지 진행할 때, 먼저 K번 이길 확률이다. K와 N의 범위는 최대 40이다. 풀이 먼저, K가 1일 때를 생각해보자. 한 번이라도 게임의 승패가 결정나면 그 순간 끝난다. 그렇기 때문에, 최대 N번까지 진행하기 위해서는 N-1번 연속으로 내리 비기다가, N번째에 이겨야 한다. 게임이 K번보다 많이 진행되기 위해서는 내가 지기도 하고, 비기기도 해야 가능하다는 것이다. 일단, $i$번 째 라운드에서 K번 이길 확률을 $f(i)$라고 하자. $i$번째까지 진행되면서 내가 질 수 있는 최대 횟수는 K-1번이다. 그리고 $i-1$번의 게임 중에서 $K-1$번을 이겼어야 하며, $i$번째 게임에서 이기는 것이다. 이를 식으로 나타내자 $$ f(i) = \frac{..

티스토리툴바