프로그래밍 diary

11057번 - 오르막 수 https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 점화식: dp[i][j] = dp[i - 1][j] + dp[i][j - 1] 마지막 자리수의 값을 기준으로 문제를 풀었다. 3자리 숫자의 경우 003, 013, 113, 023, 123, 223, 033, 133, 233, 333 이렇게 총 10가지의 오르막 수로 구성된다. 바로 위의 풀이에서 볼 수 있듯이 마지막 수를 제외한 나머지..

12865번 - 평범한 배낭 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net dp 1 2 3 4 5 6 7 1 0 0 0 0 0 13 13 2 0 0 0 8 8 13 13 3 0 0 6 8 8 13 14 4 0 0 6 8 12 13 14 -> dp[N][K] dp[2][6]은 dp[1][6]와 dp[1][2] + 8을 비교하여 더 큰 값을 가져온 것이다. 여기서 2라는 인덱스 값..

1010번 - 다리 놓기 https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 점화식: dp[n][m] = dp[n][m - 1] + dp[n - 1][m - 1] n 값이 1일 때, 경우의 수는 m의 값을 따른다. n == m 일 때, 경우의 수는 1이다. 더보기 #include #define MAX 31 using namespace std; int T, N, M; long long dp[MAX][MAX] = {0, }; int site(int n..

2156번 - 포도주 시식 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net arr[] -> 문제에서 입력 받은 포도주의 용량을 저장 dp[][] -> 선택한 포도주 잔의 용량의 합을 저장 점화식 dp[0][i] = max(dp[1][i-1], dp[2][i-1]) + arr[i] dp[1][i] = max(dp[0][i-2], dp[1][i-2], dp[2][i-2]) + arr[i] dp[2][i] = max(dp[0][i-3], dp[1][i..

10844번 - 쉬운 계단 수 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net N = 1 1, 2, 3, 4, 5, 6, 7, 8, 9 N = 2 10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98 N = 3 101, 121, 123, 210, 212, 232, 234, 321, 323, 343, 345, 454, 456, 432, 434, 543, 545, 565, 567, 654, 656, 676, 678, 765, 767, 787, 789, 876, 878, 898, 987, 989 처..

1912번 - 연속합 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 완성된 dp 배열에서 최댓값을 출력하면 문제에서 찾는 답이 된다. 점화식: dp[i] = dp[i] + dp[i-1], dp[i] = arr[i] 더보기 #include using namespace std; int n; int dp[100001] = { 0, }; int arr[100001] = { 0, }; int main() { cin >> n; for (int i = 1; i > ..

1699번 - 제곱수의 합 https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 점화식: dp[i] = dp[j * j] + dp[i - j * j] = 1 + dp[i - j * j] #include #include using namespace std; int N; int dp[100001] = { 0, }; int solution(int n) { //제곱근이 맞으면 0, 아니면 1 long long re; ..

11054번 - 가장 긴 바이토닉 부분 수열 #include #include using namespace std; int N; int arr[1001] = { 0, }; int dp_In[1001] = { 0, }; int dp_De[1001] = { 0, }; int max_Value = 0; int main() { cin >> N; for (int i = 1; i > arr[i]; } for (int i = 1; i = 1; i--) { //감소하는 부분수열의 길이 구하기 dp_De[i] = 1; for (int j = N; j > i; j--) { if (arr[j] < arr[i] && dp_De[i] < dp_De[j] + 1) dp_De[i] = dp_De[j] + 1; } } for (int..

1759번 - 암호 만들기 문제를 읽고 처음 시도한 접근은 조합입니다. 6개의 알파벳 문자 중에 4개를 선택하여 암호를 완성한다. 대신 모음은 최소 1개 자음은 최소 2개를 포함한다. 즉, 6C4(15개)를 구해서 모음이 포함되지 않았거나 자음이 1개 이하로 포함된 암호를 빼줍니다. 또, 암호는 증가하는 순서로 정렬되었을 것이라고 추측되기 때문에 sort 함수를 사용하여 미리 입력받은 알파벳 문자를 오름차순으로 정렬합니다. * 재귀를 사용하여 조합된 암호를 출력하는 combinatin 함수 public static void combination(String[] alpha, boolean[] visit, int dep, int r) { if(r == 0) { print(alpha, visit); //조합된..

2529번 - 부등호 main, dfs, comp 함수로 구성 dfs 함수는 재귀적으로 사용 (void) comp 함수는 왼쪽, 오른쪽 정수가 부등호에 부합하는지 true, false로 반환 (boolean) import java.io.*; import java.util.*; public class Main { static int k; static boolean[] visit; static List output = new ArrayList(); static StringBuilder sb; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(S..