728x90 다이나믹 프로그래밍35 [JAVA]백준 13699번: 점화식 https://www.acmicpc.net/problem/13699 13699번: 점화식 다음의 점화식에 의해 정의된 수열 t(n)을 생각하자: t(0)=1 t(n)=t(0)*t(n-1)+t(1)*t(n-2)+...+t(n-1)*t(0) 이 정의에 따르면, t(1)=t(0)*t(0)=1 t(2)=t(0)*t(1)+t(1)*t(0)=2 t(3)=t(0)*t(2)+t(1)*t(1)+t(2)*t(0)=5 ... 주어진 입력 0 ≤ n www.acmicpc.net 1. 문제 설명 점화식이 아래와 같을 때 t(n)을 출력하는 프로그램을 작성하시오. t(0)=1 t(n)=t(0)*t(n-1)+t(1)*t(n-2)+...+t(n-1)*t(0) 2. 풀이 1부터 시작해서 입력된 n까지 차례대로 점화식을 만들어 가면 된.. 2021. 8. 23. [JAVA]백준 22846번: 인증된 쉬운 게임 https://www.acmicpc.net/problem/22846 22846번: 인증된 쉬운 게임 게임 공장의 공장장인 stonejjun은 올해도 게임을 만들어내고 있다. 만들어진 게임은 검수를 거쳐 캐릭터 팀에서 만든 캐릭터들이 플레이를 하고, 이를 문제 팀에서 문제로 만들게 된다. 올해는 정 www.acmicpc.net 1. 문제 설명 모니터에 1이 쓰여있고, 칼리와 링고가 번갈아가면서 모니터에 쓰여있는 수의 약수를 하나 선택해 모니터에 있는 값에 더한다. 이때 제한 K를 초과한 사람이 패배하게 된다. 각자 최선의 전략으로 플레이를 한다고 가정하자. K가 주어졌을 때 이기는 사람은? 2. 풀이 DP로 풀 수 있는 문제이다. 모니터의 값이 x일 때부터 시작할 때 Kail가 이기면 True를 저장하는 .. 2021. 8. 18. [JAVA]백준 1102번: 발전소 https://www.acmicpc.net/problem/1102 1102번: 발전소 은진이는 발전소에서 근무한다. 은진이가 회사에서 잠깐 잘 때마다, 몇몇 발전소가 고장이난다. 게다가, 지금 은진이의 보스 형택이가 은진이의 사무실로 걸어오고 있다. 만약 은진이가 형택이 www.acmicpc.net 1. 문제 설명 고장 나 있지 않은 발전소를 이용해서 고장 난 발전기를 가동할 수 있다. 적어도 P개의 발전소가 고장나 있지 않도록, 발전소를 고치는 비용의 최솟값을 구하는 프로그램을 작성하시오. 2. 풀이 dp와 비트마스킹을 이용해서 풀 수 있다. 현재 켜져있는 발전소 상태를 bit로 표현한다면 아래와 같이 dp로 구현할 수 있다. 현재 꺼져 있는 발전소 X가 있다면 현재 켜져 있는 발전소들 중 X를 키는 .. 2021. 7. 29. [JAVA]백준 1103번: 게임 https://www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 1. 문제 설명 1부터 9까지의 숫자와, 구멍이 있는 직사각형 보드에서 게임을 한다. 가장 왼쪽 위에서 부터 시작하여 동전이 있는 곳에 쓰여 있는 숫자 X 만큼 위, 아래, 왼쪽, 오른쪽으로 이동한다. 이때 중간에 있는 구멍은 무시하며, 동전이 구멍에 빠지거나, 보드의 바깥으로 나간다면 게임은 종료된다. 최대 몇 번 동전을 움직일 수 있는지 구하는 문제이다. 2. 풀이 bfs + dp / dfs+.. 2021. 7. 19. 이전 1 2 3 4 ··· 9 다음 728x90
