백준
-
[DP] BOJ 1149 번 문제 풀이백준 문제풀이/Dynamic Programming 2019. 5. 6. 16:00
문제 분석 문제는 RGB 거리에 R,G,B 의 색으로 집을 칠하는 최소비용을 구하는 것이다. 이때, 이웃하는 집의 색은 달라야 한다. 예를 들어 G 의 인덱스가 i 라고 할 때 i + 1 과 i - 1 이 이웃하는 집이다. 우선 최소비용과 색을 포함할 수 있는 배열을 선언하자. d[i][0] = i 번째 집까지 칠할 때 최소비용 단, i 번째 집은 빨간색 d[i][1] = i 번째 집까지 칠할 때 최소비용 단, i 번째 집은 초록색 d[i][2] = i 번째 집까지 칠할 때 최소비용 단, i 번째 집은 파란색 이제 배열이 선언됐으니 점화식을 끌어내 보자. 우선 경우의 수가 하나밖에 없는 초깃값들을 초기화 하자. d[0][0] = s[0][0] , d[0][1] = s[0][1] , d[0][2] = s[..
-
[DP] BOJ 2579번 문제풀이백준 문제풀이/Dynamic Programming 2019. 5. 4. 23:35
문제 분석 각 계단을 오를 때 계단에 적혀있는 숫자의 합이 가장 큰 경우를 구하는 문제다. 조건은 다음과 같습니다. ...더보기 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 자, 지금부터 s[i] = 계단의 적힌 숫자 d[i][j] = 현재까지 j 개의 계단을 연속해서 밟고, i 번째 계단에 올라섰을 때의 점수 합의 최댓값이라고 합시다. (단, i 번째 계단은 반드시 밟는다.) 이상태에서 주어진 계단에 대해서 한번 값을 찾아봅시다. 첫 번째 계단에서는 이러한 값이 도출됩니다. d[..
-
[DP] 1463번 문제풀이백준 문제풀이/Dynamic Programming 2019. 5. 4. 13:24
문제분석 문제는 이렇습니다. 임의의 숫자를 3가지의 연산을 이용하여 1을 만들고자 할때, 연산횟수의 최솟값은 ?! 1. X가 3으로 나누어 떨어지는 경우, 3으로 나눈다. 2. X가 2로 나누어 떨어지는 경우, 2로 나눈다. 3. X 에 1을 뺀다. 예를 들어, 12이라는 숫자가 주어졌고 같이 1로 만들어 봅시다. 첫번째 12 > 4 > 2 > 1 총 3회 두번째 12 > 6 > 3 > 1 총 3회 이런식으로 3가지의 연산을 사용하면 다양한 경우의 수가 등장합니다. 그러면 이 경우의 수를 모두 따져봅시다. d[i] = i 를 1로 만드는 최소 연산 횟수 라고 정의합시다. 1. x가 3으로 나누어 떨어지면, 3으로 나눈다. d[12] = d[12/3] + 1 ...더보기 현재, 12는 3으로 나누어 떨어지..