끵뀐꿩긘의 여러가지

◎문제 링크 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net ◎문제 파악 가장 중요한 조건이자 유일한 조건이 "연속으로 놓여 있는 3잔을 모두 마실 수는 없다."는 것이다. 조건을 만족하는 포도주 배열에 새로운 잔 한잔(i번째 포도주)이 추가되었을 때, 연속으로 3잔을 먹지 않기 위해서는 마지막 3잔만 고려하여 3가지 행동을 할 수 있다. 1. 추가된 (i번째) 포도주 선택하지 않기 --> 최댓값 = i-1번째 포도주까지 있을 때와 최댓값이 같음..

◎문제 링크 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net ◎문제 파악: 계단수: 모든 자리수의 차이가 1이 나는 수 목표: N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하기 1. 1 자리 수일 때: 1~9의 수는 모두 계단수이다. 2. 2 자리 수일 때, 0으로 시작하는 수는 1의 자리에 1을 붙일 수 있다. --> 01 (1 자리 수의 배열 index 1참조) 1로 시작하는 수는 1의 자리에 0이나 2를 붙일 수 있다. --> 10,12 (1 자리 수의 배열 index 0,2 참조) 2로 시작하는 수는 1의 자리에 1이나 3을 붙일 수 ..

◎문제 링크 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net ◎문제 파악: 할 수 있는 연산 X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 입력된 숫자가 1일 경우: 연산할 필요가 없으므로 0 입력된 숫자가 2일 경우: 1. X가 3으로 나누어 떨어지지 않으므로, 3으로 나누지 않는다. 2. X가 2로 나누어 떨어지므로, 2로 나눈다. 3. 1을 뺀다. 1은 실행할 수 없으므로, 최소값은 2로 나눈 경우(연산하면 1이 된다, 최종 연산수: 1)와 1을 뺀 경우(연산하면 1이된다, 최종 연산수: 1)의 최..

◎동적 계획법, 다이나믹 프로그래밍(DP, Dynamic Programming) 분할정복 기법(큰 문제를 작은 문제로 나누어 푸는 방법)을 사용할때, 반복되는 문제의 답을 기록해 둠으로서 그 문제들을 재계산하지 않고 재사용하는 방법. Dynamic(동적)과 Programming(계획법)이라는 뜻과는 전혀 상관없다. 1. 최적 부분 구조(Optimal Substructure): 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다 2. 중복되는 부분 문제 (Overlapping Subproblem): 동일한 작은 문제를 반복적으로 해결해야 한다 의 두가지 조건을 만족할때 사용할 수 있다. ◎ DP 문제 예시-1, 피보나치 수열 피보나치 수는..