mojo's Blog

문제 링크 => Problem - C - Codeforces Problem - C - Codeforces codeforces.com Problem tags : greedy, sortings 소팅을 활용한 그리디 알고리즘 문제이다. 문제에서 주어진 n, k, x 에 대해서 알아보자면, n : the initial number of students k : the number of students you can additionally invite x : the maximum allowed level difference 주어진 Stable Groups를 문제에서 주어진 Examples를 통해 알아보려고 한다. input 8 2 3 1 1 5 8 12 13 20 22 이때 8명의 학생이 들어오고 최대 2명을 초대..

문제 링크 => 2240번: 자두나무 (acmicpc.net) 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 다이나믹 프로그래밍 문제이다. 3차원 배열 dp[x][y][z] 를 설정하였다. (x : 자두의 위치, y : 자두가 떨어지는 초 단위, z : 자두의 움직일 수 있는 횟수) 이때 주의깊게 볼 점은 z = 1 일때 움직이는 횟수를 0으로 보는것이 핵심이다. (0으로 볼 경우 배열의 index가 -1을 침범하는 경우가 발생하기 때문) 처음의 자두의 위치가 1이라고 주어질 때, 자두가 떨어질 위치가 1, 2일때의..

문제 링크 => 2293번: 동전 1 (acmicpc.net) 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 다이나믹 프로그래밍 문제이다. 오름차순으로 정렬된 동전을 통해 k원을 만족하게 되도록 하는 동전들의 개수를 구하는 문제이다. 예를들어서 동전 1원 하나만 들어왔다고 가정하자. 1 2 3 4 5 6 7 8 9 10(k) 1 1 1 1 1 1 1 1 1 1 1 이때 1원 이후로 값이 전부 채워진것을 확인할 수 있다. dp[1] = dp[1] + dp[0] (이때 dp[0] = 1 이라고 설정) = 0 + ..

문제 링크 => Problem - B - Codeforces Problem - B - Codeforces codeforces.com Problem tags : constructive algorithms, math, number theory 문제의 조건을 보면 다음과 같다. 1 is in this set. If x is in this set, x⋅a and x+b both are in this set. 예를 들어서 a=3, b=5 라고 가정해보자. 이때 1은 기본적으로 set에 포함된다. 그리고 두번째 조건을 통해 1 * 3 = 3 , 1 + 5 = 6 으로 3, 6 값이 set에 포함된다. 3을 기준으로 보면? => 3 * 3 = 9, 3 + 5 = 8 으로 9, 8 값이 set에 포함된다. 6을 기준으..

문제 링크 => 14002번: 가장 긴 증가하는 부분 수열 4 (acmicpc.net) 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 다이나믹 프로그래밍 문제 + 약간의 생각을 더 해서 풀어야하는 문제이다. 참고로 이문제는 N=1000 밖에 안되기 때문에, 이분탐색을 사용하지 않고 다이나믹 프로그래밍으로 해결이 가능하다. 그러나 문제는 가장 긴 증가하는 부분 수열을 특정지어서 값을 표현하는게 생각보다 쉽지는 않았던거 같다. 이 ..

문제 링크 => 12738번: 가장 긴 증가하는 부분 수열 3 (acmicpc.net) 12738번: 가장 긴 증가하는 부분 수열 3 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 가장 긴 증가하는 부분 수열 2 문제에서 수열의 값이 커진것을 제외하고 동일한 문제이다. [백준 12015] 가장 긴 증가하는 부분 수열 2 :: M - J - C (tistory.com) [백준 12015] 가장 긴 증가하는 부분 수열 2 문제 링크 => 12015번: 가장 긴 증가하는 부분 수열 2 (acmicpc.net) 12015번: 가장 ..