문제
석판에 있는 불순물과 보석 결정체의 정보가 주어질 때,
불순물들을 없애면서 석판을 나누고,
각 조각에 반드시 하나의 보석 결정체가 있도록
석판을 나누는 방법의 가지수를 계산하세요
생각
석판을 자르면 두 개로 나눠지는데,
이 두 개도 또 자르면 두 개로 나눠지고,
계속 자르다가 불순물은 0개 보석은 1개인게 우리가 구하고 싶은거지!
자르고 그 2개의 석판에서 만들어지는 경우의 수를 생각하고 그런 문제니까
solve(int x1, int x2, int y1, int y2)
이런식으로 어느 범위 안에서 경우를 구하는 함수를 쓰는
분할정복 방법으로 풀어야겠다 라는 생각은 쉽게 생각했지만,
리턴값을 어떻게 해줘야하는지가 어려웠다
리턴값..?
나는 재귀 문제에 약한 것 같다
기존에는 구해진 값만 리턴하면서 반환값 받으면 최대값 저장,
혹은 전역변수에 최대값 가지고 있기 이런식으로 풀다보니
'반으로 쪼개 내려가며 구할 수 있는 경우의 수 찾기' 라니.. 너무 어려웠다ㅜ
1. 맨 처음에는 단순히 불순물은 0개 보석은 1개이면 result++를 해주었다
이렇게 하니까 자르고 자르고 자르고 맨 나중에 석판이
저 조건만 만족하면 result++이 되기 때문에 엄청 큰 값을 출력하게 됌! 오노!
2. 아! 함수에서 구한 경우의 수를 int로 반환해야겠다!! 라는 생각을 함
int solve(int x1, int x2, int y1, int y2){
//근데 tempresult는 어떻게 구하지?
return tempresult;
}2-1. 처음에는 조건을 만족하는 석판을 만들면 1, 못 만들면 -1을 반환하게 했다
그리고 쪼갠 두 부분이 1을 반환하면 아! 만들 수 있구나 하고 1을 또 반환하는거지..
int solve(int x1, int x2, int y1, int y2){
//i줄에서 가로로 자른다고 하면
int tempresult1 = solve(x1, i-1, y1, y2);
int tempresult2 = solve(i+1, x2, y1, y2);
if(tempresult1 == 1 && tempresult2 == 1){
return 1;
}
}저런식으로..? ㅋㅋㅋ너무 멍청한 생각인게 웃기다 맨날 1만 정답으로 나오겠네..
2-2. 한 석판을 절반으로 나눠서,
한 쪽에서 만들어지는 경우의 수가 4가지이고, 다른 한 쪽에선 2가지라면,
총 4*2개를 만들 수 있는거라는 걸 알게됌
int solve(int x1, int x2, int y1, int y2){
//i줄에서 가로로 자른다고 하면
return solve(x1, i-1, y1, y2) * solve(i+1, x2, y1, y2);
}쪼개 쪼개 내려가면서
제일 작게 쪼갠 석판이 조건을 만족하면 1을 반환하고,
위에 단계 석판에선 구해진 경우의 수들을 곱해가면서 올라가면 되는구낭
곱하기로 되어있으니까 못 만들 때는 -1이 아니라, 그냥 그냥 0을 반환해주면 된당
(한 쪽이라도 못 만든다면 다른 한 쪽이 만들수 있어도 소용없음. 어떤 수든 0이 곱해지면 0이니까)
2-3. 근데 한 석판에서 어느 한 곳에서만 쪼개지는 게 아니라 여러곳에서 쪼갤 수 있음!
그 경우들을 다 더해주면 되겠다`~~
int solve(int x1, int x2, int y1, int y2){
int tempresult = 0;
//문제 조건 중에 잘라진 석판은 반드시 두 개의 석판이 나눠져야 한대
//그럼 맨 끝 부분들을 자르진 않으니까 범위가 x1 + 1 ~ x2 - 1 임
for(int i = x1 + 1; i< x2; i++){
if(자를 수 있으면){
//다양한 곳에서 자를 때 구해진 경우의 수들의 합이
//x1, x2, y1, y2 석판에서 만들 수 있는 경우의 수겠구나!!
tempresult += solve(x1, i - 1, y1, y2, 0) * solve(i + 1, x2, y1, y2, 0);
}
}
return tempresult;
}이런느낌으로 구현해주면 된당
2-4. 방금 자른 방향과 같은 방향으론 못 자름을 구현하기 위해
함수 인자를 추가해 세로로 자르는지 가로로 자르는지 받게되고,
//solve(int x1, int x2, int y1, int y2, int flag)
main에선 가로로 잘라라! 세로로 잘라라! 함수 두 번을 호출하는데,
이 경우들은 각각 관련이 없는 경우들이니까 합해줘야한다
//result = solve(0, n - 1, 0, n - 1, 0) + solve(0, n - 1, 0, n - 1, 1);
그냥 세로로 했을 땐 어때? 가로로 했을 땐 어때? 니까~~
코드
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <utility>
using namespace std;
vector<pair<int, int>> jewelry1;
vector<pair<int, int>> jewelry2;
int map[25][25];
//불순물, 보석 결정체 수를 세서 계속 파고 들어갈지 말지 보는 함수
int checkCase(int x1, int x2, int y1, int y2) {
int jewelry1count = 0, jewelry2count = 0;
for (int i = 0; i < jewelry1.size(); i++) {
if (x1 <= jewelry1[i].first && jewelry1[i].first <= x2) {
if (y1 <= jewelry1[i].second && jewelry1[i].second <= y2) {
jewelry1count++;
}
}
}
for (int i = 0; i < jewelry2.size(); i++) {
if (x1 <= jewelry2[i].first && jewelry2[i].first <= x2) {
if (y1 <= jewelry2[i].second && jewelry2[i].second <= y2) {
jewelry2count++;
}
}
}
//남은 불순물의 수가 보석의 수 - 1보다 작으면 의미있게 쪼갤 수 없음
//보석이 하나도 없어도 으잉- 떼잉이여
if (jewelry2count - 1 > jewelry1count || jewelry2count == 0) {
return 0;
}
//조건을 만족하는 제일 작은 석판을 만든거임!
if (jewelry1count == 0 && jewelry2count == 1) {
return 1;
}
return 2;
}
//어디서부터 어디까지 어느 방향으로 자름
int solve(int x1, int x2, int y1, int y2, int flag) {
int check = checkCase(x1, x2, y1, y2);
if (check == 0) {
return 0;
}
else if (check == 1) {
return 1;
}
int tempresult = 0;
if (flag) {
bool f = false;
for (int i = x1 + 1; i < x2; i++) {
for (int j = y1; j <= y2; j++) {
if (map[i][j] != 0) {
if (map[i][j] == 2) {
f = false;
break;
}
else {
f = true;
}
}
}
if (f) {
tempresult += solve(x1, i - 1, y1, y2, 0) * solve(i + 1, x2, y1, y2, 0);
}
}
}
else {
bool f = false;
for (int i = y1 + 1; i < y2; i++) {
for (int j = x1; j <= x2; j++) {
if (map[j][i] != 0) {
if (map[j][i] == 2) {
f = false;
break;
}
else {
f = true;
}
}
}
if (f) {
tempresult += solve(x1, x2, y1, i - 1, 1) * solve(x1, x2, i + 1, y2, 1);
}
}
}
return tempresult;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> map[i][j];
if (map[i][j] == 1) {
jewelry1.push_back(make_pair(i, j));
}
else if (map[i][j] == 2) {
jewelry2.push_back(make_pair(i, j));
}
}
}
int result = solve(0, n - 1, 0, n - 1, 0) + solve(0, n - 1, 0, n - 1, 1);
if (result) {
cout << result;
}
else {
cout << -1;
}
return 0;
}