DP (45) 썸네일형 리스트형 [백준 / BOJ] 9655 돌 게임 (Java) 문제 출처 : https://www.acmicpc.net/problem/9655 9655번: 돌 게임 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net N개의 돌이 주어지고, 두명의 플레이어(상근, 창영)가 있다. 각 플레이어는 번갈아가며 돌을 가져가는데 자신의 턴마다 1개 혹은 3개의 돌을 가져갈 수 있다. 플레이어는 매번 최선의 선택을 한다고 가정했을때, 상근이가 이기는지 창영이가 이기는지 구하는 문제다. 전형적인 게임이론 문제다. dp배열을 dp[남아있는 돌의 수][turn] = 이긴 플레이어 와 같이 설정하고 자신이 이기는경우가 있다면 항상 그 경우를 선택하면 된다. 즉, 자신이 이기는 경우가 한번이라도 존재한다면, 절대로 지지 않는다.(매번 최.. [백준 / BOJ] 23040 누텔라 트리 (Easy) 문제 출처 : https://www.acmicpc.net/problem/23040 23040번: 누텔라 트리 (Easy) 첫째 줄에 트리의 정점의 개수 $N$이 주어진다. ($2 \le N \le 100\,000$) 이후 $(N-1)$개 줄에 걸쳐 각 간선이 잇는 두 정점의 번호 $u_i$, $v_i$가 공백을 사이에 두고 주어진다. ($1 \le u_i \le N$, $1 \le v_i \le N$, www.acmicpc.net 빨간색과 검은색 정점들로 이루어진 트리가 있다. 시작은 검은색 정점, 나머지 정점은 모두 빨간색인 경우 이를 누텔라 경로라고한다. 트리에서 누텔라 경로의 갯수를 찾는 문제였다. 풀이 시간초과를 주의해야했던 문제였다. 논리는 아래와 같다. 검은색 정점에서 시작해, 거쳐간 빨간색 .. [백준 / BOJ] 23089 사탕나무 문제 출처 : https://www.acmicpc.net/problem/23089 23089번: 사탕나무 기준이 되는 사탕을 3번 사탕으로 정하면 총 5개의 사탕을 먹을 수 있다. www.acmicpc.net 트리구조의 사탕나무에 사탕이 열려있다. 안즈는 기준이 되는 사탕하나를 골라 해당 사탕부터 K이하에 있는 모든 사탕을 먹을려한다. 이때, 최대로 먹을 수 있는 사탕의 갯수를 출력하는 프로그램을 만드는 문제다. 풀이 누적 합에 DP를 이용해 푼 문제다. 문제 풀이 자체는 어렵지 않았으나, 구현시 신경써야할점이 많았었다. 구현 문제에서 어려웠던것은, K가 1초과일때(K가 1초과인 이유는 K가 1이라면, 자신의 자식만 확인하면되므로 문제되지 않기 때문이다.), K번째 자식까지 선택한 사탕의 갯수를 빠르게 .. [백준 / BOJ] 20925 메이플스토리 문제 출처 : https://www.acmicpc.net/problem/20925 20925번: 메이플스토리 첫째 줄 사냥터 수 $N$ ($1 \le N \le 200$)과 방학 기간을 분 단위로 나타낸 $T$ ($1 \le T \le 1\,000$)가 주어진다. 다음 $N$개의 줄에는 $i$번째 사냥터의 특징인 입장에 필요한 최소 경험치 $c_i$와 $1$분마 www.acmicpc.net 상원이는 메이플스토리를 할 것이다. 상원이의 캐릭터가 갈수있는 사냥터의 수 N 상원이가 사냥할 시간 T 가 주어지고, 이후, N개의 줄에 각 던전에 입장하는데 필요한 최소경험치와 시간당 주는 경험치가 주어진다. 상원이가 T시간동안 사냥했을때 얻을 수 있는 최대 경험치를 구하는 문제다. 풀이 dp로 푼 문제였다. 처음에.. [백준 / BOJ] 11049 행렬 곱셈 순서 문제 출처 : https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net N개의 행렬이 주어진다. 행렬 A의 크기를 N*M, 행렬 B의 크기를 M*K라고 할때, 각 행렬을 곱할때 필요한 곱셈 연산 수는 N*M*K이다. 모든 행렬을 곱하는데 필요한 최소 연산횟수를 구하는 문제다. 풀이 다이나믹 프로그래밍으로 풀리는 문제다. 처음엔 그리디로 생각했지만, 현재 최적값이 나중에도 최적이라는 보장이없기때문에 그리디로는 풀기 힘들어보인다. 이 문제처럼 .. [백준 / BOJ] 1099 알 수 없는 문장 (Java) 문제 출처 : https://www.acmicpc.net/problem/1099 1099번: 알 수 없는 문장 첫째 줄에 문장이 주어진다. 문장의 길이는 최대 50이다. 둘째 줄에 단어의 개수 N이 주어지며, N은 50보다 작거나 같은 자연수이다. 셋째 줄부터 N개의 줄에 각 단어가 주어진다. 단어의 길이는 최 www.acmicpc.net 몇개의 단어로 이루어진, 길이가 최대 50인 문장이 있다. 이 문장은 특이하게, 문장을 이루는 단어의 알파벳이 섞여있어도 된다. 예를들어, neotowheret 는 one two three there 중 3개의 단어를 사용해서 만들수있다. neo - > one tow -> two heret -> three heret -> there 단어를 해석할때, 각 단어의 바뀐 알.. [백준/BOJ] 9625 BABBA (Java) 문제 출처 : https://www.acmicpc.net/problem/9625 9625번: BABBA 상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했 www.acmicpc.net 버튼이 하나만 있는 기계가 있다. 버튼을 누르면 화면에있는 A가 B로 바뀌고 B는 AB로 바뀐다. 버튼을 K번 눌렀을때, 화면에 표시되어있는 A와 B의 갯수를 출력하는 문제다. 풀이 다이나믹 프로그래밍 문제다. 버튼을 K번 눌렀을때 A와 B의 갯수를 생각해보자. 1. A는 K-1번째 버튼을 눌렀을때, B의 갯수만큼 생성된다. 2. B는 K-1번째 버튼을 눌렀을때, A와 B의 갯수만큼 생.. [백준 / BOJ] 1949 우수 마을 (Java) 문제 출처 : https://www.acmicpc.net/problem/1949 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, www.acmicpc.net N개의 마을로 이루어진 나라가 있다. 나라는 1부터 N까지의 번호로 표시되며, 트리구조 , 양방향 간선 으로 이루어져있다. 각 마을에는 C명의 주민이 살고있다. (C 이전 1 2 3 4 ··· 6 다음