https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누 www.acmicpc.net 위 5개 도형 중 차례대로 4개는 DFS를 사용해서 간단히 구할 수 있다. 하지만 마지막 'ㅗ' 도형은 DFS로 만들 수 없으므로 ..
https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 0은 2와 5의 의해 계산된다. (10 = 2x5) 5의 배수는 2의 배수보다 항상 적으므로 n보다 작은 5의 배수에서 5가 몇번 곱해져있는지 계산하면 된다. 시간을 줄이기 위해, n을 5의 제곱수만큼 나눠주면 5가 총 몇번 들어있는지 바로 알 수 있다. ex) 100/5 = 20 (5의 배수가 총 20번) 100/25 = 4 (25의 배수가 총 4번) => 20+4 = 24 #include using namespace std; int main(){ ios_base::sync_wit..
https://www.acmicpc.net/problem/1149 1149번: RGB거리 RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이고, 첫 집과 마지막 집은 이웃이 아니다. 각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠하는 비용의 최솟값을 구하는 프로그램을 작성하시오. www.acmicpc.net DP문제!! i 번째까지 칠했을 때 최소 가격 = (i-1) 번째까지 칠한 가격 + i 칠한 가격 => d[i] = d[i-1] + i번째 최솟값 으로 생각할 수 있다. 하지만!! 이전을 R로 ..
