swanzzz 님의 블로그

[오늘의 문제]https://www.acmicpc.net/problem/17144[오늘의 학습 키워드]구현BFS1. 문제설명 문제를 요약하자면 미세먼지가 가득한 방에 공기청정기를 가동시켜 미세먼지를 최대 T초간 제거 후 방에 남아있는 미세먼지의 총 양을 출력하는 문제입니다. 미세먼지는 1초동안 동시에 확산을 시작하는데확산의 조건은 다음과 같습니다.미세먼지는 인접한 4방향으로 확산한다.인접한 방향에 공기청정기가 있거나, 벽이 있다면 확신이 일어나지 않는다.확산되는 양은 현재 위치 (i, j) // 5 의 양 만큼 확산된다.확산 후 현재 위치 (i, j) 에 남는 양은 확산된 미세먼지의 수 (i, j) // 5 x (확산된 미세먼지 수) 만큼 감소된다즉 i, j 는 (i, j) - (i, j) // 5 * ..

[오늘의 문제]https://www.acmicpc.net/problem/5427[오늘의 학습 키워드]너비 우선 탐색그래프 탐색, 그래프 이론구현격자 그래프1. 문제설명 상근이는 빌딩에서 탈출하려 합니다. 빌딩의 크기는 각각 N, M 으로 주어지며 상근이의 위치와, 불이 난 곳, 벽, 빈 공간의 정보가 2차원 배열에 담겨 주어집니다. 불이 매 초마다 4방향으로 번지기 시작할 때 상근이가 빌딩에서 탈출이 가능하다면 탈출에 걸린 시간을 탈출이 불가능하다면 IMPOSSIBLE을 반환하는 프로그램을 작성하는 문제 입니다.[제한사항]시간 제한 1초메모리 제한 256MB테스트 케이스는 최대 100개1 ≤ N, M ≤ 10002. 접근방식저는 우선 빌딩에 불을 모두 지르고 상근이가 탈출이 가능한지를 판별하였습니다. 불..

[오늘의 문제]https://www.acmicpc.net/problem/2133[오늘의 학습 키워드]DP구현1. 문제설명 3 x N 크기의 벽을 2x1 타일과 1x2 타일로 채우는 경우의 수를 구하는 문제 입니다. 타일의 세로 크기가 3으로 고정되어 있고 주어진 타일은 모두 2크기의 타일이므로 N이 홀수가 될 때는 타일을 제대로 채울 수 없습니다. [제한사항]시간 제한 2초메모리 제한 128MB1 ≤ N ≤ 302. 접근방식 문제를 해결하기 위해 우선 힌트를 살펴 보았습니다. 위 그림은 3 x 12 크기의 벽을 채우는 경우의 수 중 1개를 예시로 보여준 그림 입니다. 여기서 생각해 볼 수 있는 것은 1. 짝수마다 타일을 채울 수 있다. 2. 기본적으로 반복되는 기본 모양이 존재한다. 3. 규칙을 깨는 ..

[오늘의 문제]https://www.acmicpc.net/problem/2293[오늘의 학습 키워드]DP구현1. 문제설명 N 가지 동전이 주어지고 만드려는 동전의 합 K가 주어질 때 동전의 합 K를 만드는 경우의 수를 출력하는 문제 입니다. 주어진 동전은 여러번 사용해도 합이 K원 되면 상관없고, 주어진 동전을 사용한 개수가 동일한데 순서가 다른 경우 이 경우는 동일한 경우로 생각합니다.[제한사항]시간 제한 0.5초메모리 제한 4MB1 ≤ N ≤ 100, 1 ≤ K ≤ 10,000 동전의 가치는 100,000보다 작거나 같은 자연수이다. 2. 접근방식 지난 시간 풀었던 동전 2 문제와 굉장히 유사한 문제 입니다. 동전 2의 경우 주어진 경우의 수 중에서 더 적은 동전을 사용하는 경우를 골라 DP에 누적시..