본문 바로가기

알고리즘/백준77

15989번 - dp, 규칙찾기 문제:정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다.정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 10,000보다 작거나 같다. 풀이:뭔가 수학적 규칙이 있을 것 같지만, 어떤 조건이 있는지 잘 보이지 않는다.이럴때는 규칙을 찾을때 까지 써보는 것이 최고다.1234567891011121112131111211223111111211122131132111111211112211222311132133.. 2024. 8. 8.
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.

티스토리툴바