'PROGRAMMING/Algorithm' 카테고리의 글 목록 (7 Page)

[백준(BOJ)] 2156번: 포도주 시식 (Dynamic Programming, C++)

📝 문제풀이 과정 i번째 마시는 경우 i-1번째 마시는 경우: DP[i] = G[i] + G[i-1] + DP[i-3] i-1번째 안 마시는 경우: DP[i] = G[i] + DP[i-2] i번째 안 마시는 경우 DP[i] = DP[i-1] 최종 DP[i]는 i번째 마시는 경우의 DP[i]와 i번째 안 마시는 경우의 DP[i-1]에서 max로 저장한다. DP[0], DP][1] 초기값을 구해줘야 한다. DP[0]인 경우에는 이전이 없으므로 G[0] 넣어주고, 그렇지 않은 경우엔 현재와 이전 포도주 양을 넣어준다. 💻 C++ 제출코드 #include #include using namespace std; int main(){ int n; scanf("%d", &n); int G[n] = {0}; int DP..

PROGRAMMING/Algorithm 2021. 2. 19. 19:24

[백준(BOJ)] 2193번: 이친수 (Dynamic Programming, C++)

✔ 문제설명 이진수: 0과 1로만 이루어진 수 이친수(pinary number): 이진수 중 특별한 성질 가진 수 0으로 시작하지 않는다. 1이 두 번 연속 나타나지 않는다. 11을 부분 문자열로 가지지 않는다. 이친수 예: 1, 10, 101, 1000, 1001 등 📝 문제풀이 과정 DP[i][j]: i번째 자리에서 j가 오는 경우 (j는 0 또는 1) N자리 일 때, N == 1이면 DP[1][1] = 1, DP[1][0] = 0 1만 가능하므로 1일 때는 1로 카운팅, 0일 때는 0으로 카운팅한다. if(j == 1) DP[i][j] = DP[i-1][0] 현재 수가 1인 경우, 앞은 0만 올 수 있다. else if(j == 0) DP[i][j] = DP[i-1][0] + DP[i-1][1] 현..

PROGRAMMING/Algorithm 2021. 2. 12. 16:23

[백준(BOJ)] 11057번: 오르막 수 (Dynamic Programming, C++)

📝 문제풀이 과정 i는 1 ~ N까지, j는 0 ~ 9까지 범위 N = 1 한 자리일 때 0 ~ 9 (10가지) DP[i][j] = DP[i-1][k] DP[i][j](i번째 자릿수일 때, j 숫자가 올 때)는 이전(i-1)은 해당 수(i)보다 작은 수부터 해당 수(k

PROGRAMMING/Algorithm 2021. 2. 12. 01:55

[백준(BOJ)] 10844번: 쉬운 계단 수 (Dynamic Programming, C++)

📝 문제풀이 과정 DP[n]: n자리 수에서 만들 수 있는 계단 수의 개수 DP[0] = 9 (1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9) DP[n][m]에서 n이 앞자리, m이 뒷자리 초기 값: N이 1일 때, 0~9가 올 수 있으므로 DP[1][i]에 대해 count를 1로 할당해준다. 2 ~ N까지(N번째 자리) 0 ~ 9의 수가 올 수 있는데, 각 경우에 대해 점화식을 만들어준다. DP[i][0] = DP[N-1][1] : 둘째 자리가 0인 경우, 앞에는 1만 올 수 있다. (이전이 1이어야 함을 나타냄) DP[i][9] = DP[N-1][8] : 9인 경우, 주변에 8만 올 수 있다. DP[i][j] = DP[N-1][i-1] + DP[N-1][i+1] : 그 이외의 경우, 즉..

PROGRAMMING/Algorithm 2021. 2. 12. 01:47