BF2 [BF] 16937번 두 스티커 https://www.acmicpc.net/problem/16937 알고리즘 Brute Force Greedy (?) 풀이 포인트 주어진 n개의 스티커 중 두 개의 스티커만 사용하여 최대 넓이를 구한다는 점 스티커를 회전할 수 있고 스티커끼리 접할 수 있다는 점 Brute Force 전형적인 brute force 문제이다. n개의 스티커 중 2개를 골라서 스티커를 붙여보면서 최대 넓이를 가지는 스티커 조합을 찾으면 된다. 여기서 고민되는 부분이 스티커를 붙이는 것을 어떻게 구현하는지였다. 가장 먼저 생각난 점은, $h \times w$ 넓이에 한칸 한칸 for문을 돌면서 스티커를 붙여보는 것이었다. 그런데 이렇게 하면, 스티커를 붙일 수 있는 격자판과 스티커 최대 넓이가 100이므로 시간 복잡도가 꽤 커.. 2022. 1. 9. [DP] 9095, 15988번 1,2,3 더하기 https://www.acmicpc.net/problem/9095 https://www.acmicpc.net/problem/15988 알고리즘 Brute Force Dynamic Programming 풀이 포인트 같은 숫자를 여러번, 연속적으로 사용해도 된다는 점 정수 n을 구성하는 숫자의 순서는 상관 없다는 점 1+1+2, 1+2+1, 2+1+1은 모두 다른 경우의 수 정수 n을 구성하는 숫자의 개수의 제한이 없다는 점 Brute Force 문제에서 n은 11보다 작다. 따라서 n은 최대 10개의 수로 구성될 수 있다. 그러면 각 자리마다 가능한 정수 (1,2,3)를 모두 놓아봄으로써 가능한 경우 (그 정수들의 합이 n)만 체크해주면 된다. Brute Force로 프로그래밍할 때, 재귀를 이용하는 것을.. 2022. 1. 9. 이전 1 다음
