재귀(2)
-
백준 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 -
백준 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