:: ADVANCE ::

BAEKJOON ONLINE JUDGE 한국정보올림피아드 시.도 지역본선 2004 2613 숫자구슬 https://www.acmicpc.net/problem/2613 최대값의 최소값이라는 말을 보고 이진탐색이라고는 생각하였지만 처음에는 DP로 접근해 보았다.DP로도 풀이가 생각났기 때문에.. dp[start][group] : start 지점부터 끝까지 group의 개수만큼 나누었을 때 그 합 중 최대값의 최소값을 저장그룹 하나, sum값과 그 외의 구간을 group - 1개로 나누었을 때 나오는 최소값 중 최대값들 중에서 최소값을 저장해 나갔다.그리고 저장해 나가면서 그 최소값이 되는 구간의 구슬 개수 또한 저장해 나갔다. sum 값은 입력을 받으면서 이중 반복문으로 sum[start][end]에 미리 ..

BAEKJOON ONLINE JUDGE 한국정보올림피아드 시.도 지역본선 2005 2592 대표값 https://www.acmicpc.net/problem/2592 12345678910111213141516171819202122#include int count[100]; int main(){ int i, num, sum = 0, max = 0, maxNum; for (i = 0; i max) { max = count[num / 10]; maxNum = num; } } printf("%d\n%d\n", sum / 10, maxNum); return 0;}Colored by Color Scriptercs

BAEKJOON ONLINE JUDGE 한국정보올림피아드 시.도 지역본선 2005 2591 숫자카드 https://www.acmicpc.net/problem/2591 DP dp 이전까지 배치된 카드에 새로 추가된 수(한자리) 카드를 놓으면 된다. 10

BAEKJOON ONLINE JUDGE 한국정보올림피아드 시.도 지역본선 2005 2590 색종이 https://www.acmicpc.net/problem/2590 123456789101112131415161718192021222324252627282930313233343536373839#include int main(){ int count, paper[5]; for (int i = 0; i

BAEKJOON ONLINE JUDGE 2184 김치 배달 https://www.acmicpc.net/problem/2184 DPDP 테이블을 설정하기에 앞서문제를 잘 파악하면 배달을 하기위한 움직임이 왼쪽으로 이동, 오른쪽으로 이동 밖에 없으며,가는 길에 배달할 지역을 뛰어넘는 (예를 들어 10에서 출발, 9을 들리지 않고 1을 먼저 배달하는) 경우는 발생하지 않는다는 점을 알아야 한다.따라서 DP 테이블을 구간으로 잡을 수 있는데 먼저, DP[left][right] 에서 left - right 범위 내 위치한 배달할 지역은 이미 배달을 완료한 상태로 최적화가 될 수 있다.따라서 처음 공장 위치를 시작으로 범위를 점차 넓혀 나가는 식으로 탐색해 나간다. 또한 주의할 점이 하나 더 있다. 예를 들어 10..

BAEKJOON ONLINE JUDGE 한국정보올림피아드 시.도 지역본선 2004 2611 자동차 경주 https://www.acmicpc.net/problem/2611 최단경로 -> 최고 가중치(점수)를 구하는 문제 처음에는 다익스트라 알고리즘을 이용해서 풀었다.경로 출력은 경로가 이전 지점을 저장하고 있기 때문에 재귀를 이용해서 거꾸로 출력하였다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364#include #include #include using namespace std; int n;priority_queue que;vector g..

BAEKJOON ONLINE JUDGE 한국정보올림피아드 시.도 지역본선 2004 2607 비슷한 단어 https://www.acmicpc.net/problem/2607 비슷한 단어 - 같은 단어 -> 알파벳 개수 차이 없음 - 알파벳 하나 추가 또는 제거 -> 알파벳 개수 1개 차이나는 경우 1개 - 알파벳 하나 변경 -> 알파벳 개수 1개 차이나는 경우 2개 & 전체 길이 동일알파벳 개수 1개 차이나는 경우가 2개인 것만 생각할 경우 새로운 알파벳 1개씩 추가되거나 없을 때에도 같은 값을 나타내기 때문에 전체 단어의 길이도 추가로 확인해야 한다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748..

[BitMask] 에라토스테네스의 체 비트마스크를 이용한 에라토스테네스의 체 구현 에라토스테네스의 체는 빠르게 동작하기 때문에 수행 범위를 늘릴 때 부담이 되는 것은 시간보다는 메모리이다.체를 구현 할 때 범위 내의 각 정수들의 소수 여부를 저장하기 위해 범위 만큼의 배열 크기를 선언해 두었어야 했는데 비트마스크를 이용하여 이를 줄일 수 있다. 이는 예를 들어 unsigned char로 배열을 잡을 경우 8bit를 사용하여 8개의 정수의 소수 여부를 1 or 0으로 표현, 이를 담은 하나의 정수로 저장하면 된다.또한 type의 크기 이후 정수를 저장하려면 다음 배열에 다시 그 이후 8개의 정수 소수 여부를 한번에 저장한다. prime[0] -> 0부터 7까지의 소수 여부 저장 : 10101100 (7 :..

BAEKJOON ONLINE JUDGE 11726 2xn 타일링 https://www.acmicpc.net/problem/11726 DP 만들 수 있는 경우를 직접 만들어 보면 규칙을 찾을 수 있다. 이전 경우에서 | 막대 하나를 더 추가하는 경우와 이전, 이전 경우에서 = 막대를 추가하는 경우따라서 dp[i] = dp[i - 1] + dp[i - 2] (피보나치 수열과 같은 식)을 얻을 수 있다. 1234567891011121314151617181920212223242526272829303132333435363738#include #include #define Max(x, y) (x > y ? x : y) int n, m;int dp[1002][1002];int map[1002][1002]; int s..

BAEKJOON ONLINE JUDGE 11048 이동하기 https://www.acmicpc.net/problem/11048 1234567891011121314151617181920212223242526272829303132333435363738#include #include #define Max(x, y) (x > y ? x : y) int n, m;int dp[1002][1002];int map[1002][1002]; int solve(int y, int x) { int *res = &dp[y][x]; if (*res != -1) return *res; if (map[y][x]