본문 바로가기

알고리즘90

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 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.
BOJ 15462 - The Bovine Shuffle(usaco silver, dfs) https://www.acmicpc.net/problem/15462 int arr[] : 각 위치에 소가 몇마리 있는지 int odr[] : 다음 위치 가리키는 배열 int mcnt[] : 각 위치마다 배치됐던 소의 최소값. 초기상황 : 배열에 소가 1마리씩 들어있음 위치에 따라 다음 이동 위치가 주어지기 때문에 dfs, bfs를 생각했으나 현재 상태를 어떻게 표현해야할지 감이 안와서 이런 생각을 해봤다. "무한히 시뮬레이션 하는데 제한시간이 주어졌다는 것은 반복되는 상태가 생긴다는 뜻이고, bfs dfs로 풀 수 있다는 건 시뮬 돌리다보면 시간 안에 답이 나온다는 뜻이니까 시간에 맞게 최대한 시뮬 돌려보면 나오지않을까?" shuffle 1회에 O(1e5), 전체 O(le8)안에 끝내야 하므로 시뮬을 1.. 2019. 10. 9.

티스토리툴바