링크: https://www.acmicpc.net/problem/17521문제보자마자 주식 문제가 생각났다.주식 문제들은 최대 이익을 내기 위해서 그리디하게 행동하면 된다. 값쌀 때 사서 값비쌀 때 팔면 된다.이 문제에서는 늘어난 코인만큼 다시 투자를 할 수 있으니, 상승 곡선이면 무조건 사는것이 이득이다. (늘어난 코인을 배로 불릴 수 있으니)코드 직관적으로 풀었지만 내심 불안했다.그래서 dp로도 풀어보았다. 물론, 같은 결과가 나왔고 정답이다.점화식은 dp[k] := k일까지 벌 수 있는 최대 코인이다.\(i < j\) 인 \(i\)일째에 가진 돈으로 전부 매수하고, \(j\)일에 모두 매도한다면 (두 날짜 사이의 변폭) * (i일에 살 수 있었던 코인의 수)만큼 벌 수 있을것이다.

https://www.acmicpc.net/problem/5612 문제 1분 단위로 터널에 들어간 차량의 수와 터널에서 나온 차량의 수가 주어졌을 때, 터널에는 차량이 최대 몇 대 있었는가? 풀이 처음에 터널에 있었던 차량 수에서, 매분 들어간 차량의 수를 더하고 나간 차량의 수를 빼면 된다. 중간에 한번이라도 터널 안 차량의 수가 음수가 되면 0을 출력하는 것에 주의하면 정답. 코드

[이전 블로그의 글] 각 노드에서 리프 노드까지의 거리가 (왼쪽으로 가든지, 오른쪽으로 가든지) 같도록 조정하는 것이므로 재귀를 생각할 수 있다. 이를 해결할 작은 문제로 재귀의 중간 과정부터 생각했다. 왼쪽과 오른쪽의 길이가 달라져서 조정이 필요한 상황은 "왼쪽 != 오른쪽" 이다. 이를 조정하는 작업은 더 작은 쪽에 가중치를 증가시키는 것이다. 가중치는 보정을 위해 추가하는 것이므로, 맞추고자 하는 차이만큼 증가시키면 된다. 코드 보기

링크 1: https://uva.onlinejudge.org/...problem=1859 링크 2: BOJ 2133 - 타일채우기(https://www.acmicpc.net/problem/2133) 문제 타일 시리즈 중에 하나로, 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 문제이다. 풀이 3×n 크기의 벽을 채우는 경우의 수를 \(f(n)\)이라고 하자. 다음은 전개될 수 있는 모든 모양이다. 모양이 반복되는 경우까지만 적었다. .... x... .... f(n) = .... g(n) = .... or .... .... .... x... A..... AA.... A..... or ...... ...... ...... A..... ACC... ACC... ACC... A..... -> A....

링크: https://www.acmicpc.net/problem/17142 문제 연구소에 이미 존재하는 바이러스들 중 \(m~(2\le m \le 10)\)개를 활성 상태로 바꾸어 바이러스를 퍼뜨리는 문제이다. 그 때, 연구소의 모든 빈칸에 바이러스가 퍼지게 하는 최소 시간을 구해야 한다. 풀이 연구소에 존재하는 바이러스 들 중 \(m\)개를 골라야한다. DFS 같은 방법으로 고를 수 있지만, next_permutation을 사용하면 간단하다. 4개 중 2개를 고르는 조합은 0011 → 0101 → 0110 → 1001 → 1010 → 1100 순으로 진행된다. 이런 특징을 사용하여 매번 적당히 \(m\)개를 선택하여 플러드 필(Flood Fill, BFS)을 한다. 모든 빈칸을 방문한다면 그 때의 탐색..

링크: https://www.acmicpc.net/problem/17140 문제 R 연산을 기준으로 구현하고, C 연산은 행/열만 바꿔서 똑같이 진행하면 된다. 한 행을 읽고 map과 같은 적당한 자료구조에 (수, 등장한 횟수)의 형태로 저장한다. 삽입과 조회, 수정 모두 \(O(logN)\) 만큼 걸린다. 정렬 기준은 1. 등장한 횟수가 적은 순, 2. 수의 크기가 작은 순이다. 정렬을 위해 map에 저장된 내용을 추출한다. 반복자 등으로 자료구조를 순회하면서 (수, 등장한 횟수)를 배열로 바꿔 정렬하고, 정렬된 순서로 새로운 행에 덮어씌운다. 바로 덮어씌워도 상관없으나, 이전 행보다 길이가 짧아지는 경우에 주의해야한다. (ex. [3, 1, 1, 1, 1, 1] → [3, 1, 1, 5, 0, 0] ..

링크: https://www.acmicpc.net/problem/14852 문제 타일 시리즈 중 하나인데, 2×N 크기의 벽을 2×1, 1×2, 1×1 크기의 타일로 채우는 경우의 수를 구하는 문제이다. 먼저 왼쪽부터 타일을 채워가면서 생기는 모양에 따라 부분 문제를 만들어나간다. 아래와 같은 모양을 각각 \(f(n), g(n)\)이라고 정의해보자. \(g(n)\)은 첫 번째 열 중에서 한 칸만 채워진 경우이다. 두 모양이 채워질 수 있는 Base case를 이렇게 정의하자. \(f(0)\)은 모든 타일을 채웠다는 뜻으로 1개로 센다. \(g(0)\)은 불가능한 모양이므로 0이다. 먼저 \(g(n)\)은 아래와 같이 세 가지 모양으로 전개될 수 있다. 첫 번째 열의 빈칸에 1×1짜리 타일을 하나 채우면 ..

링크: https://www.acmicpc.net/problem/9375문제해빈이가 가진 의상들의 이름과 종류가 주어지면, 가능한 모든 경우의 수는 몇 개인지 묻는 문제입니다.문제에서 같은 이름을 가진 의상은 존재하지 않으므로 이름은 중요하지 않고 해당 종류만 구분하면 됩니다.가지고 있는 모자가 2개라면 모자만으로 가능한 경우는 3가지입니다. 첫 번째를 쓰거나, 두 번째를 쓰거나, 아무것도 쓰지 않거나 이렇게 총 3가지입니다. 어떤 종류를 \(n\)개 가지고 있다면 선택 가능한 수는 \(n+1\)개이고, 나올 수 있는 모든 가짓수는 각 종류마다 가능한 경우를 모두 곱한 값입니다.위 그림의 경우에는 \(3 \times 4 \times 2~=~24\) 이지만, 문제에서 알몸이 아닌 상태 즉 모두 선택하지 않..