본문 바로가기

알고리즘/백준 & swacademy108

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.
BOJ 15590 - Rental Service (usaco silver, 그리디, 구간합배열, 이분탐색) https://www.acmicpc.net/problem/15590 그리디 + 이분탐색 + 구간합배열로 풀었다. 생각한 순서는 1. 모든 소 N마리에 대해 i번쨰 소를 우유를 팔거나, 빌려주거나 하는 완탐 -> (O(2^1000000) 시간초과 2. 소의 우유 산출량을 내림차순 정렬한 후, 0~i번째 소는 우유를 팔기로 한다면, i+1~n-1번쨰 소는 반드시 빌려줘야 한다. 빌려주는 경우는 간단하게 처음부터 더해주면 되기 떄문에 그에 맞는 구간합배열을 저장해 뒀다면 상수시간에 도출할 수 있다. 문제는 0~i번째 소의 우유를 팔때의 수익을 반환하는 함수의 논리이다. 그냥 앞에서부터 긁어주면 O(i)로 할 수 있는데, 이렇게 되면 시간 초과가 난다. (p,q)를 q에 대해서 내림차순으로 정렬한다면, 다음과 .. 2019. 10. 11.

티스토리툴바