다이나믹 프로그래밍 (34) 썸네일형 리스트형 [백준 / BOJ] 9655 돌 게임 (Java) 문제 출처 : https://www.acmicpc.net/problem/9655 9655번: 돌 게임 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net N개의 돌이 주어지고, 두명의 플레이어(상근, 창영)가 있다. 각 플레이어는 번갈아가며 돌을 가져가는데 자신의 턴마다 1개 혹은 3개의 돌을 가져갈 수 있다. 플레이어는 매번 최선의 선택을 한다고 가정했을때, 상근이가 이기는지 창영이가 이기는지 구하는 문제다. 전형적인 게임이론 문제다. dp배열을 dp[남아있는 돌의 수][turn] = 이긴 플레이어 와 같이 설정하고 자신이 이기는경우가 있다면 항상 그 경우를 선택하면 된다. 즉, 자신이 이기는 경우가 한번이라도 존재한다면, 절대로 지지 않는다.(매번 최.. [백준 / BOJ] 23089 사탕나무 문제 출처 : https://www.acmicpc.net/problem/23089 23089번: 사탕나무 기준이 되는 사탕을 3번 사탕으로 정하면 총 5개의 사탕을 먹을 수 있다. www.acmicpc.net 트리구조의 사탕나무에 사탕이 열려있다. 안즈는 기준이 되는 사탕하나를 골라 해당 사탕부터 K이하에 있는 모든 사탕을 먹을려한다. 이때, 최대로 먹을 수 있는 사탕의 갯수를 출력하는 프로그램을 만드는 문제다. 풀이 누적 합에 DP를 이용해 푼 문제다. 문제 풀이 자체는 어렵지 않았으나, 구현시 신경써야할점이 많았었다. 구현 문제에서 어려웠던것은, K가 1초과일때(K가 1초과인 이유는 K가 1이라면, 자신의 자식만 확인하면되므로 문제되지 않기 때문이다.), K번째 자식까지 선택한 사탕의 갯수를 빠르게 .. [백준 / BOJ] 2533 사회망 서비스(SNS) 문제 출처 : https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net N명의 친구들이 서로 트리 형태로 연결되어있다. 친구들은 자신의 친구들이 모두 얼리어답터 일때, 자신도 얼리어답터가 된다. 이때, 모든 친구를 얼리어답터를 만들기위해 필요한 초기 얼리어답터 수를 구하는 문제다. 풀이 다이나믹 프로그래밍으로 푼 문제다. 트리에서의 DP의 전형적인? 유형으로 DP로 풀리는것을 떠올리는것이 문제였다. 아이디어 트리의 현재 노드에 할수있는 연산은 두 .. [백준 / 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] 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 [백준 / BOJ] 7579 앱 (Java) 문제 출처 : https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 스마트폰 백그라운드에 켜져있는 N개의 애플리케이션중 몇개의 애플리케이션을 종료해서 M만큼의 메모리를 확보하고싶다. 각 애플리케이션을 종료할때얻는 메모리양과 종료할때 필요한 비용이 주어질때, M만큼의 메모리를 확보하기위해 필요한 최소 비용을 구하는 문제다. 풀이 knapsack 문제였다. 개인적으로 dp배열을 생각하는게 어려웠다. 2차원 배열을 이용해 푸는것은 맞는것 같은데, M이 10,00.. 이전 1 2 3 4 5 다음