본문 바로가기

분류 전체보기327

BOJ 14863 - 서울에서 경산까지 ( KOI 초등, knapsack ) https://www.acmicpc.net/problem/14863 딱봐도 냅색이라 바로 풀었는데.. int f(int k, int t) { if (k == N) return 0; //계산의 통일성을 위해서 f(n,양수) = 0 이라고 함. int& ret = dp[k][t]; if (ret != -1) return ret; ret = IMP; int time1 = opt[k].first.first, money1 = opt[k].first.second; int time2 = opt[k].second.first, money2 = opt[k].second.second; if (time1 2019. 10. 15.
BOJ 10835 - 카드게임 ( 2015 KOI 초등, dp ) https://www.acmicpc.net/problem/10835 왼쪽 더미 i번째, 오른쪽 더미 j번째를 보고 있을 때 다음으로 선택할 수 있는 경우의 수가 최대 3가지 이다. bfs로 풀어야되나? 싶었는데 i,j 외에 여태 얻은 값을 세번째 상태로 계속 넘겨줘야 해서 visited공간이 부족하고, map으로 구현하기도 비효율적이다. dp로 풀기로 해서 점화식을 짜 봤는데 깔끔하게 짜 졌다. 이후 코드로 옮기기만 했다. #include #include using namespace std; int n, a[2000], b[2000], dp[2000][2000]; int f(int i, int j) { if (i == n || j == n) return 0; int& ret = dp[i][j]; if (.. 2019. 10. 14.
BOJ 10834 - 벨트( KOI 초, 오버플로우 ) https://www.acmicpc.net/problem/10834 반성용 게시글 문제는 볼 필요도 없고 ans = (ans/a)*b; 가 핵심 코드인데, ans는 a로 나누어 떨어지는 입력만 준다. ans= (ans*b)/a;가 자꾸 틀렸습니다가 떠서 30분정도 삽질했는데, ans*b에서 오버플로우가 났었다. #include #include #include using namespace std; int main() { int n; cin >> n; int cnt = 0; int ans = 1; for (int i = 0,a,b,s; i > a >> b >> s; if (s == 1) cnt++; ans = (ans / a) * b; } cout a >> b >> s; if .. 2019. 10. 14.
BOJ 10165 - 버스노선 ( KOI 고, 라인스위핑 ) https://www.acmicpc.net/problem/10165 m^2 이하의 논리가 생각나지 않아서 풀이를 찾아봤던 문제..ㅜㅜ https://milkclouds.github.io/2019/02/09/BOJ-10165-%EB%B2%84%EC%8A%A4-%EB%85%B8%EC%84%A0/ 이 글을 참고했습니다. 감사합니다... reg in reg, reg in irreg, irreg in irreg으로 상황을 나누셨던데, 이 상황들의 합집합이 모든 상황을 나타내면서 교집합이 없다... regular in regular의 상황일때 논리가 인상깊다. [a,b]를 a는 오름차순, b는 내림차순으로 정렬하고 순서대로 처리하면, 현재 보고 있는 노선의 end가 여태 나온 end의 최대갑인 lastEnd보다 작.. 2019. 10. 13.

티스토리툴바