알고리즘 (371) 썸네일형 리스트형 [구름톤 챌린지] 3주차 11일차 통증 (2) 문제 구름-그라운드 게임에는 통증이라는 시스템이 있다. 통증 수치가 높다면 게임에서 승리하기 어려워지므로, 아이템을 적절히 사용해 통증 수치를 $0$으로 유지하는 것이 중요하다. 게임 안에는 통증 수치를 감소시켜 주는 아이템이 $2$종류가 있다. 아이템의 이름은 $A, B$이고, 각 아이템을 사용 시 각각 $A_p, B_p$만큼 통증 수치를 감소시켜 준다. 각 아이템은 원하는 만큼 획득할 수 있다. 플레이어는 적과의 전투에서 피해를 입어 현재 $N$의 통증 수치를 가지고 있다. 플레이어가 통증 수치를 $0$으로 줄이기 위해 필요한 아이템의 최소 개수를 구해보자. 단, 사용했을 때 통증 수치가 $0$보다 작아지는 아이템은 사용할 수 없음에 유의하시오. 입력 첫째 줄에 플레이어의 통증 수치를 나타내는 정수 .. [구름톤 챌린지] 2주차 10일차 GameJam 문제 플레이어는 GameJam에 참가했다. GameJam은 현장에서 즉석으로 팀을 꾸려 게임의 규칙을 만든 뒤, 생각한 규칙을 코드로 옮겨서 게임을 만들어내는 대회이다. 플레이어가 속한 팀은 보드로 즐길 수 있는 간단한 보드게임을 만들었다. 게임의 진행 방법과 규칙은 다음과 같다. 게임은 한 변의 길이가 $N$인 격자 보드 위에서 진행한다. 보드는 한 변의 길이가 $1$인 $N^2$개의 칸으로 나누어져 있다. 각 칸에는 에 해당하는 방향으로 칸만큼 한 칸씩 이동하라는 지시가 적혀있다. 플레이하는 사람은 처음에 보드의 칸 중 하나에 말을 올려놓는다. 각 칸에 적힌 지시대로 말을 이동한다. 만약 이동 중에 보드 밖으로 나가게 된다면 반대쪽의 첫 번째 칸으로 이동한다. 예를 들어 맨 오른쪽 칸에서 오른쪽으로 .. [구름톤 챌린지] 2주차 9일차 폭탄 구현하기 (2) 문제 $N \times N$ 크기의 정사각형 모양의 땅이 있다. 땅을 $1 \times 1$ 크기의 작은 땅으로 나누었을 때, 위에서 $y$번째, 왼쪽에서 $x$번째에 위치한 땅의 좌표를 $(y, x)$로 나타낸다. 추가로 모든 땅에는 폭탄 값이라고 하는 값이 있다. 모든 폭탄 값의 초기 값은 $0$이다. $K$개의 폭탄을 이 땅 위에 떨어트리려고 한다. 어떤 $1 \times 1$ 크기의 땅 위에 폭탄을 떨어트리게 되면 폭탄이 떨어진 땅과, 그 땅에 상하좌우로 인접한 칸의 폭탄 값에 영향을 끼친다. 폭탄 값이 변하는 정도는 땅의 상태에 따라 다르다. $N \times N$ 크기의 영역 밖이거나, 땅의 상태가 # 이라면 폭탄 값은 변하지 않는다. 땅의 상태가 0 이라면 폭탄 값은 $1$ 증가한다. 땅의 .. [구름톤 챌린지] 2주차 8일차 통증 문제 구름-그라운드 게임에는 통증이라는 시스템이 있다. 통증 수치가 높다면 게임에서 승리하기 어려워지므로, 아이템을 적절히 사용해 통증 수치를 $0$으로 유지하는 것이 중요하다. 게임 안에는 통증 수치를 감소시켜 주는 아이템이 $3$종류가 있다. 아이템의 이름은 bandage, medicine, painkiller 이고, 각 아이템을 사용 시 $1, 7, 14$만큼 통증 수치를 감소시켜 준다. 각 아이템은 원하는 만큼 획득할 수 있다. 플레이어는 적과의 전투에서 피해를 입어 현재 $N$의 통증 수치를 가지고 있다. 플레이어가 통증 수치를 $0$으로 줄이기 위해 필요한 아이템의 최소 개수를 구해보자. 단, 사용했을 때 통증 수치가 $0$보다 작아지는 아이템은 사용할 수 없음에 유의하시오. 입력 첫째 줄에 .. [Python] 13255번 동전 뒤집기 https://www.acmicpc.net/problem/13255 13255번: 동전 뒤집기 첫째 줄에 동전의 개수 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 K (1 ≤ K ≤ 50)이 주어진다. 셋째 줄에는 A[i] (1 ≤ A[i] ≤ N)가 주어진다. www.acmicpc.net 23/08/23 최근 확률 DP 문제를 계속 공부하고 있다. 이 문제 또한 확률 DP 문제로 쉽게 해결할 수 있다. 또한, 약간의 최적화를 거치면 매우 빠르게 문제를 해결할 수 있다. 첫번째 접근 방식: 첫 번째로 접근한 방식은 나이브한 $3$차원 확률 DP이다. DP테이블은 다음과 같이 정의했다. $$DP[i][j][k] = i번째 \ 뒤집는 \ 행위를 \ 수행했을 \ 때 \ j번째 \ 동전이 \ k번 .. [Python] 12046번 Not So Random (Small) / 12047번 Not So Random (Large) https://www.acmicpc.net/problem/12046 12046번: Not So Random (Small) The first line of the input gives the number of test cases, T. T test cases follow; each consists of one line with six integers N, X, K, A, B, and C. Respectively, these denote the number of machines, the initial input, the fixed number with which www.acmicpc.net https://www.acmicpc.net/problem/12047 12047번: Not So Random (Large.. [구름톤 챌린지] 2주차 7일차 구름 찾기 깃발 문제 구름 찾기 게임은 한 변의 길이가 $N$인 격자 모양의 게임판 $M$에서 진행하는 게임이다. 게임판의 일부 칸에는 구름이 숨겨져 있고, 게임판에 숨겨진 모든 구름의 위치를 찾으면 게임에서 승리할 수 있다. 구름 찾기 게임의 제작자인 플레이어는 조금 더 쉽게 구름을 찾을 수 있도록 도와주는 깃발을 게임판 위에 설치하려고 한다. 깃발은 구름이 없는 칸이면서, 상하좌우와 대각선으로 인접한 여덟 칸 중 구름이 하나 이상 있는 칸에만 설치할 수 있다. 이렇게 설치한 깃발에는 인접한 여덟 칸 중 구름이 있는 칸의 개수에 해당하는 값이 적힌다. 플레이어는 깃발을 세울 수 있는 모든 칸에 깃발을 세워두었다. 문득, 플레이어는 깃발 중 값이 $K$인 깃발이 몇 개나 있는지가 궁금해졌다. 여러분이 플레이어를 대신해 .. [Python] 7670번 Game Dice https://www.acmicpc.net/problem/7670 7670번: Game Dice In the game of Dungeons & Dragons, players often roll multi-sided dice to generate random numbers which determine the outcome of actions in the game. These dice come in various flavors and shapes, ranging from a 4-sided tetrahedron to a 20-sided isocahedro www.acmicpc.net 23/08/21 최근 확률 DP문제를 계속 공부하고 있다. 복습하고자 글로 남긴다. 문제 접근 방식: DP로 접근했으며, DP테.. 이전 1 ··· 21 22 23 24 25 26 27 ··· 47 다음
