-
(백준 1780번 종이의 개수 C++) 라이님 블로그 대회 알고리즘 따라잡기 4) 분할 정복(Divide and Conquer) 2탄PROGRAMMING/알고리즘 2024. 1. 8. 21:02
후후 이번주도 1일 1알고리즘 가즈아~!
이전 포스팅은 여기에!↓
2024.01.07 - [알고리즘] - (백준 1992번 쿼드트리 C++) 라이님 블로그 대회 알고리즘 따라잡기 4) 분할 정복(Divide and Conquer) 1탄
(백준 1992번 쿼드트리 C++) 라이님 블로그 대회 알고리즘 따라잡기 4) 분할 정복(Divide and Conquer) 1탄
아직 못 푼 그리디 문제가 몇 개 있지만 잠시 묻어두고 분할 정복을 시작하고자 한다! ↓ 자세한 설명은 아래 라이님 블로그를 참고! ↓ https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220776241154&paren
jjo-mathstory.tistory.com
백준 1780번
https://www.acmicpc.net/problem/1780
1780번: 종이의 개수
N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수
www.acmicpc.net
개인적으로 쿼드 트리랑 비슷해서 쉬울거라고 생각했는데...
놀랍게도 똑같은 실수를 했다😶
//1780 종이의 개수 #define _CRT_SECURE_NO_WARNINGS #include <cstdio> #include <vector> #include <utility> int cnt1 = 0, cntm1 = 0, cnt0 = 0; void Add(const int a) { if (a == -1) { cntm1++; return; } if (a == 0) { cnt0++; return; } if (a == 1) { cnt1++;return; } } // 종이의 갯수를 세는 함수 , 분할정복, 3개의 sub문제로 나눔 void CountPaper(int**Arr, int N, int x, int y) { if (N == 1) { Add(Arr[x][y]); return; } std::vector<std::pair<int, int>> StartPoint = { {0,0}, {0, N / 3.}, {0, 2. * N / 3.}, {N / 3., 0}, {N / 3., N / 3.}, {N / 3., 2. * N / 3.}, {2. * N / 3., 0}, { 2. * N / 3., N / 3. }, { 2. * N / 3., 2. * N / 3. } }; int temp = Arr[x][y]; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (Arr[i+x][j+y] != temp) { if (N == 3) { for (int _i = 0; _i < 3; _i++) { for (int _j = 0; _j < 3; _j++) { CountPaper(Arr, N / 3, x+ _i, y+ _j); } } } else { for (int k = 0; k < 9; k++) { CountPaper(Arr, N / 3, x + StartPoint[k].first, y + StartPoint[k].second); //x, y 빼먹지마!!!!! } } return; } } } Add(temp); return; } int main() { int N; scanf("%d", &N); int** Arr = new int* [N]; for (int i = 0; i < N; i++) { Arr[i] = new int[N]; { for (int j = 0; j < N; j++) scanf("%d", &Arr[i][j]); } } CountPaper(Arr, N, 0, 0); printf("%d\n%d\n%d", cntm1, cnt0, cnt1); for (int i = 0; i < N; i++) delete[]Arr[i]; delete[]Arr; return 0; }
생각보다 2차원을 분할하면 기준점이 헷갈린다. 특히 맨 처음에는 기준점을 (0,0)으로 두기 때문에 머릿속 머리디버깅에서는 문제가 없는 경우가 많고, 크기가 작은 예제를 돌리면 모두 정답처럼 보인다.
나 역시 반례를 찾지 못해서 고생하다가 결국 질문게시판을 뒤졌는데...! 개쩌는 반례를 누가 알려주셔서 그걸로 해결했다.
진짜 반례 못 찾으면 피눙물난다.. https://www.acmicpc.net/board/view/64880
글 읽기 - 반례좀 찾아주세요 ㅠㅠ
댓글을 작성하려면 로그인해야 합니다.
www.acmicpc.net
선생님 감사합니다.. 따봉 하나는 제꺼에요...⭐ 27 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
안되시는 분들 이거 해보세요,, 답은 0 24 1 나와야 합니다...
진짜 집단지성으로 오늘 문제도 해결!!!
세상에 똑똑한 선생님들이 너무 많아서 공부하기 너무 좋은 세상이다
굴러가는게 너무 신나서 주석 처리 안하고 제출했더니 출력 초과..>< 'PROGRAMMING > 알고리즘' 카테고리의 다른 글