분할정복(4)
-
백준 1992번: 쿼드트리 (C++)
https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 풀이 분할 정복 문제인걸 바로 알았지만 항상 분할 정복, 재귀는 머리가 아프다. partition 함수를 호출하면 시작부터 끝부분 중에 하나라도 다른 숫자가 있으면 chk 를 false 로 바꿔주었고 false 일 때 4개로 분할해서 재귀를 호출하고 true 일 때 숫자를 저장했다. 괄호 없이 출력하는 건 쉬웠는데 괄호를 어떻게 출력시켜주어야할 지 고민하는 과정이 오래걸렸다. stri..
2023.02.17 -
백준 2630번: 색종이 만들기 (C++)
https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 풀이 1780 종이의 개수와 거의 비슷한 문제. paper[2] 에 각각의 종이의 개수를 넣어주었다. partition 함수를 보면, 종이를 전부 탐색하고 가장 왼쪽 상단의 숫자와 다른 숫자가 있을 때 chk를 체크해주었다. chk에 따라 전체가 같은 색이면 paper[]의 숫자를 추가시켰다. 그리고 하나라도 다른 부분이 있을 경우 4가지 부분으로 나누어서 똑같이 반복 ..
2023.01.26 -
백준 1780번: 종이의 개수 (C++)
https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 풀이 9개 부분으로 분할해야 하는 분할 정복 문제. -1, 0, 1 - 3가지 종이가 있어서 cnt[3] 을 선언해서 각각 넣어주려고 한다. partition 함수를 보면, 종이를 전부 탐색하고 가장 왼쪽 상단의 숫자와 다른 숫자가 있을 때 tmp_cnt를 체크해주었다. tmp_cnt에 따라 전체가 같은 색이면 cnt[ paper + 1 ]의 숫자를 추가시켰다. 그리고 하나라도 다른 부..
2023.01.26 -
백준 24460번: 특별상이라도 받고 싶어 (C++)
https://www.acmicpc.net/problem/24460 24460번: 특별상이라도 받고 싶어 첫 번째 줄에는 정수 $N$이 주어진다. (단, $N = 2^m$, $0 \le m \le 10$, $m$은 정수) 두 번째 줄부터 $N$개 줄의 $i$번째 줄에는 $i$번째 줄에 있는 의자에 적힌 추첨번호가 주어진다. 각 줄에는 $N$개의 추첨 www.acmicpc.net 풀이 분할 정복 문제. 개념이 이해가 안되서 유형 부수기 중. 사실상 재귀 문제인데 어떻게 설계하는 지가 중요한 듯 하다. 4가지 의자 중에 2번째로 숫자가 작은 의자를 골라야해서 ans[4] 배열에 4가지 분할 된 함수의 값을 넣고 ans[1]을 리턴하면 재귀적으로 ans[4] 배열에는 2번째로 작은 의자만 담기게 된다. 사실 ..
2023.01.26