본문 바로가기

전체 글132

15486 - 퇴사2(dp) 문제:15486번: 퇴사 2 (acmicpc.net) 풀이:전형적인 dp를 이용하는 문제라고 볼 수 있다.dp는 Dynamic Programming의 약자로 동적 계획법이라는 뜻이다.즉, 하나의 큰 문제를 여러개의 작은 문제로 나누어 푼다는 뜻이다.위의 문제를 풀기 위한 가장 좋은 방법은, 각 일수별로 얼마를 버는게 최대 이익일지 체크하며,마지막날 까지 진행하는 것이다.예를들어 7일차에 벌 수 있는 최대 금액을 구하려면, 6일차를 알아야하며, 6일차를 알려면 5일차를 알아야한다.이렇게 1일차까지 거슬러가므로, 각 일수에 따라 최대 금액을 구하며 마지막날의 최대 금액을 구해야 한다. 각 일수별로 최대 금액을 산정하려면 어떤 일수에서, 어떤 경우의수를 고려해야하는지 미리 저장해두면 좋을 것이다.예를들어 2일.. 2024. 8. 7.
16930번 - 달리기(BFS) 문제: 진영이는 다이어트를 위해 N×M 크기의 체육관을 달리려고 한다. 칸은 빈 칸 또는 벽이다. x행 y열에 있는 칸은 (x, y)로 나타낸다. 매 초마다 진영이는 위, 아래, 오른쪽, 왼쪽 중에서 이동할 방향을 하나 고르고, 그 방향으로 최소 1개, 최대 K개의 빈 칸을 이동한다.첫째 줄에 체육관의 크기 N과 M, 1초에 이동할 수 있는 칸의 최대 개수 K가 주어진다.둘째 줄부터 N개의 줄에는 체육관의 상태가 주어진다. 체육관의 각 칸은 빈 칸 또는 벽이고, 빈 칸은 '.', 벽은 '#'으로 주어진다.마지막 줄에는 네 정수 x1, y1, x2, y2가 주어진다. 두 칸은 서로 다른 칸이고, 항상 빈 칸이다.(x1, y1)에서 (x2, y2)로 이동하는 최소 시간을 출력한다. 이동할 수 없는 경우에는 .. 2024. 8. 6.
17086번 - 아기상어2(BFS, 8방향 탐색) 문제:N x M(둘다 50이하) 크기의 공간에 아기 상어 여러마리가 있다. 상어가 있으면 1, 없으면 0 이다.어떤 칸의 안전 거리는 그 칸과 가장 거리가 가까운 아기 상어와의 거리이다. 두 칸의 거리는 하나의 칸에서 다른 칸으로 가기 위해서 지나야 하는 칸의 수이고, 이동은 인접한 8방향(대각선 포함)이 가능하다.안전 거리가 가장 큰 칸을 구해보자.  풀이:첫번째 칸 부터 안전거리를 찾는 것은 비효율적이라는 생각이 들었다.N x M 만큼 각 칸의 안전거리를 찾아야 하기 때문이다.상어의 위치가 주어지기에, 상어의 위치를 기준으로 찾으면 좋겠다고 생각했고,각 상어의 위치로부터 각 칸의 안전거리를 따로 따로 측정하며, 그 중 가장 작은 안전거리를 저장하면 될 것이라 생각했다.그러기 위해 머저 아래와 같이 전.. 2024. 8. 4.
14226번 - 이모티콘(bfs) 문제:영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다.영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만들어 보려고 한다.화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.화면에 있는 이모티콘 중 하나를 삭제한다.모든 연산은 1초가 걸린다. 또, 클립보드에 이모티콘을 복사하면 이전에 클립보드에 있던 내용은 덮어쓰기가 된다. 클립보드가 비어있는 상태에는 붙여넣기를 할 수 없으며, 일부만 클립보드에 복사할 수는 없다. 또한, 클립보드에 있는 이모티콘 중 일부를 삭제할 수 없다. 화면에 이모티콘을 붙여넣기 하면, 클립보드에 있는 이모티콘의 개수가 화면에 추가된다.. 2024. 7. 31.

티스토리툴바