https://www.acmicpc.net/problem/3114 3114번: 사과와 바나나 첫 번째 예제의 경우 불도저가 오른쪽-아래, 오른쪽-아래, 아래로 이동하면 된다. 경로의 아래에 있는 사과 나무의 개수는 3+2+4=9개이고, 위에 있는 바나나 나무의 개수는 3+5=8개이다. www.acmicpc.net 문제조건 아래(↓), 오른쪽(→), 오른쪽아래(↘)로 갈수 있는 불도저가있고, 오른쪽 맨 아래칸까지 이동한다. A(불도저 아래쪽, 사과), B(불도저 위쪽, 바나나) 사과와 바나나의 합의 최댓값의 경우는? 처음 문제를 봤을땐, 탐색을 진행하는 경우의 수인것같아서 BFS로 접근했다. 하지만 이 접근방법은 최소일때 구하기 용이한 방법으로 생각을 좀더 했다. 우선 Brute Force를 떠올렸는데, ..

https://www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net 문제조건 어떤 문자열을 팰린드롬으로 분할한다. 분할된 수의 최솟값을 출력 팰린드롬이란? 어떤 문자가 있을때, 거꾸로 뒤집어서 읽어도 똑같은 문자를 의미한다. ex) 기러기 ☞ 기러기(O) cf) 거북이 ☞ 이북거(X) 이 문제에서 핵심은 문자가 입력으로 들어왔을때, 문자열안에서의 모든 경우의수를 탐색해서 팰린드롬인지 각각 파악해야..

https://www.acmicpc.net/problem/2228 2228번: 구간 나누기 N(1 ≤ N ≤ 100)개의 수로 이루어진 1차원 배열이 있다. 이 배열에서 M(1 ≤ M ≤ ⌈(N/2)⌉)개의 구간을 선택해서, 구간에 속한 수들의 총 합이 최대가 되도록 하려 한다. 단, 다음의 조건들이 만족되 www.acmicpc.net 문제조건 각 구간은 한개이상의 연속된 수로 이뤄짐 서로다른 두 구간은 겹쳐있거나, 인접하면 안됨 정확히 M개의 구간이어야함 뭔가 좀처럼 접근방법이 떠오르지 않았다. 계속해서 경우의수가 다르기 때문에 DFS로 완전탐색을 돌려야하나 ,,? 어떻게 풀지 감이안와서 접근 방법만 찾아봤다. 역시 dynamic programming,,, 왠지 감이 안잡힌다 생각했다. 식을 세워야하는..