문제 https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 풀이 방법 (0,0)부터 시작해서 (10,10)까지 종이에 1이 적혀있으면 큰 색종이부터 작은 색종이까지 붙일 수 있는 종이를 다 붙혔다 뗐다하면서(백트래킹) 깊이 우선 탐색을 한다. 2580번 스도쿠와 비슷할 수도 있는 문제. 코드 #include #include #include using namespace std; int answer = 0x6FFFFFFF; void dfs(ve..
백트래킹
문제 https://www.acmicpc.net/problem/10597 10597번: 순열장난 kriii는 1부터 N까지의 수로 이루어진 순열을 파일로 저장해 놓았다. 모든 수는 10진수로 이루어져 있고, 모두 공백으로 분리되어 있다. 그런데 sujin이 그 파일의 모든 공백을 지워버렸다! kriii가 순 www.acmicpc.net 풀이 방법 한 자릿수 또는 두 자릿수로 끊어 공백을 만들고, 만들어진 수열의 길이가 N일 경우 출력하는 문제이다. 공백으로 분리한 수를 이미 사용했으면 더 진행하지 않고 멈추는 가지치기와 실행했던 과정을 되돌리는 백트래킹을 사용한다. 주의할 점은 성공 케이스에서 조건비교인데, 아래 코드처럼 수열의 개수로 해도 되고 다른 풀이처럼 만들어진 수열의 가장 큰 수로 비교해도 된다..
