PS
BOJ 11053 가장 긴 증가하는 부분 수열
boj 11053 가장 긴 증가하는 부분 수열 D[i]가 어떻게 작동해야 문제에서 원하는 답을 잘 찾아낼 수 있을까를 생각해봤다. 위 그림과 같이 작동해야하는데, 그래서 D[i]를 i번째 원소를 마지막으로 하는 가장 긴 부분 수열의 길이라고 정의하였다. a[i]는 수열을 담는 배열이다. D[i]는 길이이기에 1씩 점점 증가하는 방식으로 식을 정의해줘야하는데, 언제 1씩 증가시켜야하는지 조건을 정해주는 것이 이 문제의 핵심이다. 먼저 코드를 보고 코드에 대해 설명해보겠다. #include #include using namespace std; int n; int mx; int a[1005]; int D[1005]; int main(void) { ios_base::sync_with_stdio(0); cin.t..
BOJ 7576 토마토
boj 7576 토마토 BFS로 풀 수 있는 문제다. 조금 독특한 점은 시작점이 여러 곳이 될 수 있다는 것이다. 전체를 다 돌아보고 시작점이 될 수 있는 곳을 다 찾아 한번씩 bfs를 다 돌려보는 풀이가 가장 먼저 생각났지만, 최대 시간복잡도가 O((NM)^2)이 될 수 있어 이 방법으론 풀 수 없다. 그래서 토마토 정보를 입력받을 때, 익은 토마토의 시작점을 전부 큐에 넣어주고 bfs를 돌리는 방식으로 문제를 풀었다. 익은 토마토의 경우 거리 dis 값이 전역변수이니 0으로 채워지고, 안 익은 토마토는 dis 값을 -1로 둔다. 코드를 한번 보자. #include #include #include #include using namespace std; int n, m; int board[1005][100..
BOJ 2156 포도주 시식
boj 2156 포도주 시식 포도주 잔을 마시는 경우를 맨 마지막 포도주 잔의 상태에 따라 나눌 수 있다. 맨 마지막 포도주 잔을 안마시는 경우 맨 마지막 포도주 잔을 마시는데, 그 잔이 연속된 첫번째 잔인 경우 맨 마지막 포도주 잔을 마시는데, 그 잔이 연속된 두번째 잔인 경우 그림으로 표현하면 다음과 같다. arr는 포도주 잔의 양을 담는 배열이고, D[i]는 i번째 잔까지 포도주를 최대로 마시는 양으로 테이블을 정한다. D[i] = D[i-1] D[i] = D[i-2] + arr[i] D[i] = D[i-3] + arr[i-1] + arr[i] 위 세 가지를 비교해서 가장 큰 값을 D[i]로 결정하면 된다. 코드로 구현해보자. #include #include using namespace std; i..
BOJ 9465 스티커
boj 9465 스티커 위 그림과 같이, 문제의 조건에 따라 변을 공유하는 스티커는 뗄 수 없고, 대각으로만 이동하며 뗄 수 있다. 이 때, 대각으로 이동할 수 있는 경우는 아래 그림과 2가지가 있다. 3칸부터는 이동하면 중간에 거쳐갈 수 있는 칸이 무조건 있으므로 가장 높은 점수를 구하는 문제 조건에 어긋나므로 제외한다. 맨 위 그림을 보면, 스티커를 떼는 경로는 마지막에 떼지는 스티커가 첫번째 줄이냐 두번째 줄이냐로 나눠진다. 테이블 D[i][j]는 j번째 줄의 i번째 칸까지 스티커 점수의 최댓값으로 정의하고, score는 스티커의 점수를 담는 배열이다. 그러면 위의 내용을 점화식으로 정의해보자. D[i][0] = max(D[i-1][1], D[i-2][1]) + score[i][0] D[i][1] ..
BOJ 2193 이친수
boj 2193 이친수 쉬운 계단 수, 오르막 수와 비슷한 류의 문제이다. 길이가 N인 이친수의 경우의 수를 끝이 0이거나 1인 경우로 나눈다. 초기 값으로는 길이가 1일 때와 2일 때를 잡고, 그 값을 쌓아올려 길이가 N일 이친수의 갯수를 구한다. 길이가 3 이상인 이친수의 경우, 끝이 0인 경우 그 앞의 수로 0, 1이 올 수 있다. 끝이 1인 경우는 그 앞의 수로 0만 올 수 있다. 이를 바탕으로 테이블 D[i][j]를 길이가 i이고 맨 끝 수가 j인 이친수의 갯수로 정의하고 점화식을 설정했다. j가 0일 때, D[i][j] = D[i-1][j] + D[i-1][j+1] j가 1일 때, D[i][j] = D[i-1][j-1] 점화식을 바탕으로 코드를 구현했다. #include using namesp..