다이나믹 프로그래밍

[Python] 백준 11051 : 이항 계수 2

문제 11051번: 이항 계수 2 [ 문제 조건 ] nCk 를 구하면 된다. [ 해결순서 ] 먼저 분류가 DP라서 DP로 해결하려 했다. 팩토리얼 값들을 저장하기 위해 dp배열을 선언해서 반복해서 곱한 값들을 배열에 저장하였고 계산 된 값을 그냥 공식에 맞게 출력했다. nCn이나 nC0인 경우는 값이 그냥 1이기 때문에 조건문을 추가하였다. ( 넣지않아서 에러가 발생했다 ) 파이썬에 내장되어 있는 factorial 모듈도 있길래 그것도 사용해서 풀어봤다. 3줄만에 풀 수 있었다 ! ✏️한줄평 : 재귀적으로 팩토리얼을 구하지 않고 dp로 풀어볼 수 있는 문제였다. 코드

[Python] 백준 1309번 : 동물원

1309번: 동물원 [ 문제 조건 ] 2 * N 배열의 동물원 우리 사자를 배치할 때 가로 세로로 붙어있으면 안됨 사자가 한마리도 없는 경우도 1가지 경우로 침 [ 해결순서 ] 처음엔 기존의 dp 같은 방식으로 풀려고 시도해 배열의 각 칸에 숫자를 부여해서 조건에 맞는 조합으로 값을 계산해서 구하려고했다. 뭔가 규칙이 보이는 것 같다가도 막상 식을 못세우겠어서 조금 헤매다 결국 구글의 도움을 좀 받았다. ( 삽질을 하고있단 느낌이 .. ) 첫번째 줄에 경우를 3가지로 나눠서 계산을 해야한다. *4번 줄 참고 경우의 수를 나눈 후 제일 작은 예시인 2 X 2 배열일 때를 직접 적어가며 규칙을 찾아보려했다. 사진을 참고하면 이해가 빠르겠지만, 한마리도 두지 않는 경우는 ( 두지 않는 경우, 왼쪽, 오른쪽 )..

[Python] 백준 1932 : 정수 삼각형

문제 https://www.acmicpc.net/problem/1932 [ 문제 조건 ] 한 줄씩 내려가면서 합이 최대가 되는 경로 구하기 더해질 수 있는 값은 대각선 왼쪽 or 오른쪽 [ 해결순서 ] 누적 값이 더해질 배열을 0으로 초기화 해서 입력받은 배열의 길이와 같게 선언 및 초기화 ( 그냥 입력받은 배열에다가 계산해도 무관하다 ) 예제를 분석하다 보니 가로 줄의 첫번째 값과 끝 값은 비교 대상이 없으므로 그냥 전 줄의 같은 인덱스 값을 더하면 되고, 처음, 끝을 제외한 인덱스 값들은 이제 대각선 왼쪽 or 오른쪽을 비교해서 더 큰 값을 현재 값에 더해준다. 그렇게 값을 누적시키면 맨 마지막 줄에 이제 여태까지 누적된 경우의 수가 배열에 저장 그 중 최대 값을 구해 출력한다. [ 예제 풀이 ] ✏..

[Python] 백준 11052번 - 카드 구매하기

문제 11052번: 카드 구매하기 [ 문제 조건 ] 카드 개수 < 가격 i개의 카드, 가격은 Pi 즉, 가격을 최대값으로 구해야 한다. [ 예제 풀이 ] #1장 샀을때 최대가격 dp[1] =1 dp[1] = dp[1], dp[0] + list[1] #2장 샀을때 최대가격 dp[2] = 5 dp[2] = dp[2], dp[1] + list[1] #1 + 1 (1장짜리 2개) dp[2] = dp[2], dp[0] + list[2] #0 + 5 (2장짜리 1개) #3장 샀을때 최대가격 dp[3] = 6 dp[3] = dp[3], dp[2] + list[1] #5 + 1 (2장짜리 1개 + 1장짜리 1개) dp[3] = dp[3], dp[1] + list[2] #1 + 5 (1장짜리 2개 + 2장짜리 1개) d..

[JAVA] 백준 11057 - 오르막 수

문제 11057번: 오르막 수 [ 문제 조건 ] N의 범위는 1~10000 오르막 수의 개수를 % 10007 [ 해결순서 ] 직접 노트에 적어보면서 규칙을 찾으려고 했다.이를 보면 점화식을 구할 수 있다. 이를 보면 점화식을 구할 수 있다. 각 자릿수별로 끝자리 0~9에 따라 들어갈 수 있는 경우의 수를 구해 해당 n의 경우의 수를 모두 더하면 총 오르막 수 의 개수를 구할 수 있다. 점화식 : dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) ✏️한줄평 쉽다고 생각했지만, 조금 생각을 해봐야하는 신박한 문제였다. 코드

[JAVA] 백준 1149번 - RGB거리

문제 1149번: RGB거리 [ 해결순서 ] 처음엔 첫 줄의 최소 값을 구하고 다음 줄에는 그 줄의 색깔을 제외한 색깔 중 최소 값을 구하려 했다. 그러면 전체에서의 최소 값을 구하지 못함. 결국 전체 경우의 수를 구해야 함 해당 값을 구하려면 현재의 색깔을 제외한 색깔의 행과, 직전의 열을 값들을 비교해서 작은 값에 + 현재의 비용을 더함. (비용을 더하지 않는 실수를 함) 마지막 줄의 색깔 중 가장 작은 값이 정답 점화식 dp[i][red]=Math.min(dp[i-1][blue],dp[i-1][green])+cost[i][red] //빨간 색 이라면, 그 전줄의 빨간 색이 아닌 파랑, 초록 중 작은 값 + 해당 값의 가격 ✏️한줄평 DP 문제를 더 자주 풀어 익숙하게 해야겠다. 코드