목록2016/09 (20)
:: ADVANCE ::
BAEKJOON ONLINE JUDGE 11052 붕어빵 판매하기 https://www.acmicpc.net/problem/11052 DPdp[n] = Max(i개 세트 가격 + 나머지 붕어빵 개수의 최대값) 1. top-down 12345678910111213141516171819202122232425262728293031323334353637#include #define Max(x, y) (((x) > (y)) ? (x) : (y)) int n;int cost[1001];int dp[1001]; int solve(int num){ int i; if (num == 0) return 0; if (dp[num]) return dp[num]; dp[num] = cost[num]; for (i = 1; i
BAEKJOON ONLINE JUDGE 11507 오르막 수 https://www.acmicpc.net/problem/11057 오르막 수1. dp[ n 번째 수가 ] [ i 일 때 ] 오르막 수 = n - 1번 째수가 i보다 같거나 큰 수들의 오르막 수들의 합 즉, 5자리 수 일 때 첫째 자리에 1이 오면 두번째 자리에 1, 2, 3, .... 9가 올 수 있고, 이 수들을 처음 수로 하는 4개의 오르막 수들이 다 올 수 있기 때문에 모든 그러한 경우의 수들을 다 합하면 된다. 12345678910111213141516171819202122232425262728293031323334353637#include int n;int dp[1001][10]; int solve(){ int i, j, k; int..
BAEKJOON ONLINE JUDGE 한국정보올림피아드 시.도 지역본선 2005 2594 놀이공원 https://www.acmicpc.net/problem/2594 풀이 > 입력된 시간을 -10분, +10분 해서 저장한 후운행 시작 시간을 기준으로 정렬그 후 운행 시간을 시작과 종료 시간을 이어나가는데 가장 늦게 끝나는 시간과 이어지지 않는 시작시간을 만나면 rest time으로 계산 및 최대값 찾기 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#include #include using namespace std; struct Data { int start, end;};..
BAEKJOON ONLINE JUDGE 한국정보올림피아드 시.도 지역본선 2005 2593 엘리베이터 https://www.acmicpc.net/problem/2593 1차 풀이 : DPinput을elevator[층] : 각 층에서 갈 수 있는 엘리베이터 번호fl[엘리베이터 번호] : 각 엘리베이터에서 갈 수 있는 층들을 vector로 저장 dp[floor][elevator] : floor를 elevator로 도착할 때의 최소 이동 (floor 없어도 될 듯)이동할 때 각 elevator를 중점으로 이동 요즘 DP 공부 중이라 DP 적으로 접근했는데 over한 듯...답이 맞기는 하였지만 시간이 60ms가 나오기도 했고 이 풀이는 영 아닌것 같아서 다시 접근 1234567891011121314151617..
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..