1099 알 수 없는 문장 (G3) dp[i] = i번째 문자까지 만들 수 있는 최소 비용 http://boj.kr/2f180cfc6e6f445b98191f366c8a98a6 1082 방 번호 (G3) dp[i] = i원을 사용해서 만들 수 있는 가장 큰 방 번호 http://boj.kr/a6889080f221488e92ca74fea010ec92 2248 이진수 찾기 (G3) 이항계수의 성질을 이용해서 범위 안의 combination 값들을 미리 계산해준다. 그리고 가장 높은 자리부터 내려가면서 i-1개 자리에서 L개 이하의 1개 배치될 수 있는 모든 경우의 수보다 현재 I가 크다면 현재 자리에 1을 넣는다. 그렇지 않다면 0을 넣는다. 이런식으로 I번째 이진수를 구할 수 있다. http://boj..
11657 타임머신 (G4) 벨만포드 알고리즘을 수행한다. 거리 배열을 구할 때 데이터 타입 범위에 주의하자. long long을 사용해야 한다. http://boj.kr/5de133d5fa8140b399f4a77308c66fc4 5052 전화번호 목록 (G4) 전화번호들을 사전순으로 정렬한 다음에 인접한 번호끼리 비교한다. 만약에 앞의 번호가 뒤의 번호의 접두어가 된다면 일관성이 없다고 판단할 수 있다. http://boj.kr/42a1be5b39594611bbae780a7ebc36fd 14852 타일 채우기 3 (G4) dp[n] = 2*n 크기의 벽을 2*1,1*2,1*1 크기의 타일로 채우는 경우의 수 그림을 그려보면서 타일의 끝부분에 주목하면 점화식을 유도할 수 있다.dp[n] = 2*dp[..
12996 Acka (G3) dp[i][j][k] = dotorya가 a곡, kesakiyo가 b곡, hongjun7이 c곡 불렀을 때 앨범을 만들 수 있는 방법의 수 http://boj.kr/bdc634c727a04427a168e6dc58fe44b7 14505 팰린드롬 개수 구하기 (Small) (G3) dp[i][j] = s[i:j+1]의 부분 수열 중 팰린드롬의 개수 http://boj.kr/09b6e26c69a34dc187a26a8b45a23944 1823 수확 (G3) dp[i][j] = v[i:j+1]까지 벼가 남았을 때 얻을 수 있는 최대 이익 http://boj.kr/01f888a3ed214dbe9295b5d0467a6d1b 5015 ls (G3) dp[i][j] = 패턴의 처음 i개..
1106 호텔 (G4) dp[i] = 고객 i명을 유치하기 위해 필요한 최소 비용 http://boj.kr/eda56c043fe04b94863a76278da6f9a4 2624 동전 바꿔주기 (G4) dp[i] = i원을 만들 수 있는 방법의 수 http://boj.kr/0c30a754956b47ba8af519f7861feffb 12869 뮤탈리스크 (G4) dp[a][b][c] = SCV 3개의 체력이 각각 a,b,c일 때, SCV들을 모두 파괴하는 데 필요한 최소 공격 횟수 SCV의 체력이 최대 60이므로 상태 공간을 60*60*60으로 설정한다. BFS를 돌리면서 최소 공격 횟수를 dp 테이블에 기록한다. 최종 정답은 모든 SCV가 파괴된 상태인 dp[0][0][0]이다. http://boj.kr..
8913 문자열 뽑기 (G3) 문자열의 길이가 최대 25이므로 모든 경우에 대해서 재귀적으로 각 그룹들을 제거하면서 빈 문자열이 되는지 확인하면 된다. http://boj.kr/d0f8be3020c64594a794f24b69baf0d6 11062 카드 게임 (G3) dp[i][j] = i에서 j까지의 카드들이 남아 있을 때, 근우가 가져갈 수 있는 최대 점수 근우가 카드를 가져갈 때, 가장 왼쪽 카드 또는 가장 오른쪽 카드를 가져갈 수 있다. 이 때 명우가 최적의 선택을 했을 경우 남아있는 카드들 중에서 명우가 얻는 점수를 뺀 값을 근우의 점수로 기록한다. http://boj.kr/9d3a5872aab64fe6b3ac294b7ac8d865 14428 수열과 쿼리 16 (G1) 세그먼트 트리로 구간의 ..
1949 우수 마을 (G2) dp[node][0] = 해당 노드를 선택하지 않았을 때, 자식 노드에서 얻을 수 있는 최대 주민 수dp[node][1] = 해당 노드를 선택했을 때, 자식 노드에서 얻을 수 있는 최대 주민수 위와 같이 정의하고 DFS를 이용해서 트리에서의 DP 테이블을 계산해준다. 최종 정답은 루트 노드에서 선택한 경우와 선택하지 않은 경우 중 최댓값이다. http://boj.kr/ff3f639352ba41309973b3102f4e1ff1 14267 회사 문화 1 (G4) 상사에서 부하로 이어지는 단방향 트리를 만든다. 이후 칭찬에 대한 정보가 주어질때마다 매번 DFS를 돌리는것이 아니라 칭찬의 시작점에만 기록을 해놓는다. 그리고 루트에서부터 DFS를 한번만 돌리면서 칭찬을 누적해서 더해..
28706 럭키 세븐 (G5) 선택지를 모두 고른 이후 결과로 나온 K가 7의 배수가 되도록 할 수 있는지 판단하면 되므로 매 턴마다 modular 7한 결과값만 들고 다니면 된다. set으로 결과값들을 관리했다. http://boj.kr/6aed488c749c43d1920d15d2cf259ef5 8901 화학 제품 (G5) AB,BC,CA 세 가지 조합을 만들 수 있는 모든 경우를 확인한다. http://boj.kr/7970c2bd2c654a45bcb24575041fe6aa 17025 Icy Perimeter (G5) 가장 큰 컴포넌트를 찾는다. 그러한 컴포넌트가 여러 개 있으면 둘레가 작은 것이 답이다. DFS/BFS 중 아무거나 이용하면 된다. http://boj.kr/ad36b1b6f96444..
2482 색상환 (G3) d[i][j] = i개의 색 중에서 j개의 색을 인접하지 않게 선택하는 경우의 수 (초기 조건 설정)d[i][1] = i : i개의 색 중에서 1개의 색을 선택하는 경우는 i가지가 존재한다.d[i][0] = 1 : i개의 색 중에서 0개의 색을 선택하는 경우는 1가지이다. (점화식)d[i][j] = d[i-2][j-1] + d[i-1][j]d[i][j]를 구할 때, i번째 색을 선택하는 경우에는 i-1번째 색은 선택할 수 없으므로 i-2개의 색에서 j-1개의 색을 선택하는 경우와 같다. i번째 색을 선택하지 않은 경우에는 i-1개의 색에서 j개의 색을 선택하는 경우와 같다. (최종 정답)d[n-3][k-1] + d[n-1][k]색깔들이 원형으로 있으므로 첫 번째 색과 마지막 색이..
14466 소가 길을 건너간 이유 6 (G3) 모든 소들의 쌍에 대해서 다리를 건너지 않고 인접한 칸으로 이동해서 도착할 수 있는지 확인해주면 된다. BFS/DFS 중 아무거나 이용해도 된다. http://boj.kr/95aadfb791fa4472a470b95b2aa37c5c 14452 Cow Dance Show (G4) 무대 크기 K가 될 수 있는 범위 안에서 답을 가정하고 parametric search를 한다. min heap을 이용해서 현재 K가 가능한지 판단한다. 초기에는 무대에 K마리의 소가 동시에 올라가고 그 후로는 가장 먼저 춤을 끝낸 소가 무대에서 내려가는 시간에 다음 소가 무대에 오르게 된다. 공연이 Tmax 내에 끝난다면 더 작은 K값을 탐색하고 그렇지 않다면 더 큰 K값을 탐색한다..
16500 문자열 판별 (G5) dp[i]를 문자열 S의 처음부터 i번째 문자까지의 부분 문자열을 만들 수 있는지를 나타내는 boolean 값으로 정의한다. 초기값으로 dp[0]은 true이다. 이는 빈 문자열을 만들 수 있다는 의미이다. dp[i]를 계산하기 위해 j를 0부터 j-1까지 순회하면서 dp[j]가 true이고 s[j:i]가 단어 목록 A에 포함되는지 확인한다. 만약 그렇다면 dp[i]를 true로 설정한다. 이와 같이 O(N^2)에 테이블을 채울 수 있다. 최종 정답은 dp[n]이다. http://boj.kr/19f69b00d92f4ed2a4162ba4fd28893c 3987 보이저 1호 (G5) 탐사선의 위치에서 위,아래,오른쪽,왼쪽 4방향으로 모두 시그널을 보내본다. 시뮬레이션을 잘 ..