BOJ 백준 20667 크롬 문제: https://www.acmicpc.net/problem/20667 20667번: 크롬 첫 줄에는 N, M, K 값이 주어진다. (N ≤ 100, M ≤ 1,000, K ≤ 100,000) N 은 총 크롬 탭 수이다. M 은 목표 CPU 사용량이다. K 은 목표 메모리 할당량이다. 다음 N 줄에는 다음과 같이 크롬 탭의 정보가 www.acmicpc.net N개의 탭 중 일부 탭을 지워서 CPU 사용량을 M 이상, 메모리 사용량을 K 이상 확보하면서 지운 탭의 중요도의 합을 최소로 하는 것을 목표로 한다. 이 때의 중요도 합의 최솟값을 구해야 한다. 우선 이 문제는 다이나믹 프로그래밍(Dynamic Programming)으로 해결해야 한다. 그러면 여기서 다이나믹 프로그..

BOJ 백준 10160 암호 문제: https://www.acmicpc.net/problem/10160 10160번: 암호 새로 바뀐 KOI 웹사이트의 암호는 N개의 영문 알파벳 대문자로 이루어진다. 특별히 암호는 영문 알파벳 중 처음 K개를 사용해서 만든다. 예를 들어, K=5이면, ‘A', 'B', 'C', 'D', 'E'만으로 암호를 만들 www.acmicpc.net 길이가 N이고 영문 알파벳 중 처음 K개의 알파벳을 사용해서 만든 암호 중 안전한 암호의 개수를 구한다. 여기서 ‘안전한 암호’란 “ABCBC” 또는 “ABABC” 패턴이 없는 암호를 의미한다. 처음에는 여집합을 이용해서 구하는 방법을 고민했다. 전체 암호의 개수에서 안전하지 않은 암호의 개수를 구하면 안전한 암호의 개수를 알 수 있기..

​​ BOJ 백준 5444 시리얼 넘버 문제: https://www.acmicpc.net/problem/5444 N개의 기타가 존재하고, 이 중에는 강토가 갖고 있는 기타가 있다. 강토가 소유하는 기타의 시리얼 넘버를 모두 합한 값은 M의 배수이다. N개의 모든 기타의 시리얼 넘버와 M이 주어졌을 때, 가능한 강토의 기타 개수의 최댓값을 구해야 한다. 다음과 같은 배열을 정의하면 동적 프로그래밍(Dynamic Programming)으로 해결 가능하다. dp[i][j]: i번째 기타까지 봤고, 이 중에서 강토가 갖고 있는 기타의 시리얼 넘버 합을 M으로 나누었을 때의 값이 j일 때의 가능한 강토의 기타 개수의 최댓값 아래는 풀이 과정을 정리한 것이다. 1) 우선 dp 배열 값을 모두 -1로 초기화한다. 2..