열심히해보겠씁니다

동전이 최소가 되도록 n 가지 동전을 이용해 k 원을 만든다. n이 100가지이고 10만 보다 작거나 같은 가치이며, k는 1만 원 이하이다. 사용한 동전의 구성이 같은데 순서가 다르면 같은 경우이다. -> 순열이 아닌 조합으로 풀 수 있다. 가치가 같은 동전이 여러 개 있을 수 있으므로 중복된 검색은 피할 수 있다. k원을 만들었을 때 동전의 최소 개수만 알면 되므로 Dynamic Programming 을 이용한다. 1. dp 배열 정의) dp[k] = k 원 일때 사용한 최소 동전의 개수로 정의한다. 2. 기저사례) dp[0] = 0, dp[동전 1개 가치] = 1 이 기저 사례이다. 3. 점화식) dp[i] = max(dp[i], dp[i - 동전 1개 가치] + 1) 개이다. #include #i..

Codeforces Codeforces codeforces.com 구글 코드잼이 2023년을 마지막으로 사라집니다... 더 이상 훌륭한 사람들을 뽑으러 큰 대회를 진행할 필요가 없을 정도로 구글의 위상이 높아지기도 했고, 코드잼 자체를 비용으로 생각하게 되었기 때문에 힘들어지는 지금 시기에 대규모 lay off와 더불어 사라진 것 같네요. 그래서 상시 대회가 열리는 codeforces 로 가보도록 합시다. 이미 꽤나 역사가 되었기 때문에 꽤나 공신력이 있습니다. 백준처럼 남의 코드를 제출해도 랭크가 오르는 것과는 다르게 특정 요일 특정 시간에만 풀 수 있는 대회가 열리고, 빠르고 정확하게 풀수록 랭크가 많이 오릅니다. 회원가입/로그인을 하고 메인에 들어가봅시다. 무슨 페이지인지도 모르겠네요 ㅋㅋ 자세히 ..

두 배열을 주고, 두 배열의 연속된 부분집합의 합이 특정 숫자 T를 만족하는 개수를 찾으란다.. T 는 -10억 ~ 10억이고 A, B 배열은 1000개 까지 있다. 각 배열의 값은 -1백만 ~ 1백만이다. 일단 배열의 부분집합수만 해도 Sigma(1000) 이니 각 50만개가 넘는다. 두 개 결합하는 경우의 수는 50만 x 50만이므로 2초 안에 불가능하므로 필요한 경우만 빠르게 찾는 것이 목표다. 나는 두 가지를 이용해서 간편하게 풀길 원했다. 1. presum 2. lower bound, upper bound 문제에서 연속된 부분집합만을 요구하므로 미리 구간합을 계산하여 가지고 있을 수 있다. 예를 들어, A 가 [1,2,3,4,5] 라면 presum = [1, 2, 3, 4, 5, 1+2, 2+3..

최소값/최대값을 구하는 dp 문제이다. 다만 이 경우에 메모리가 4MB 가 한정되어 있으므로 최소한의 메모리를 사용하면 된다. N 이 10만이고 3칸이므로 30만 x int = 1.2MB 정도를 차지하므로 dp 10만 짜리 배열을 하나 추가로 쓰거나 할 수 있지만 ladder 1 x 3 하나와 dp 2 x 3 2개로도 풀 수 있다. 귀찮아서 ladder 는 그냥 다 받기로 했다. 사다리는 다음과 같이 작동한다. 1 2 3 4 5 6 이 있을 때, 1번은 4, 5 번, 2번은 4,5,6번 3번은 5,6 번으로만 내려갈 수 있으므로 4번의 최댓값은 max(1번 + 4번, 2번 + 4번) 이고, 최소값은 min(1번 + 4번, 2번 + 4번) 이다. 5번의 최댓값은 max(1번 + 5번, 2번 + 5번, 3번..

소가 들어가고 싶은 축사가 정해져있고, 한 축사에 한 마리씩 넣으면 된다. 최대유량이나 이분매칭으로 구하면 된다. 훨씬 간단한 이분매칭으로 풀었다. 소 그룹을 A, 축사 그룹을 B 라고 뒀을 때, 소 3마리, 축사 4개가 있고 S1 = [ 1, 2, 3 ] S2 = [ 1, 2, 3, 4 ] S3 = [ 2, 3, 4 ] 일 때를 생각해보자. 그럼 그래프를 다음과 같이 그릴 수 있다.소 1번부터 차례대로 원하는 축사를 고른다고 생각해보자. 1번 소가 1번 축사를 고른다. 그 후 2번 소가 고를 차롄데 2번 소도 1번을 가고 싶다. 그럼 2번 소를 1번 축사에 넣고 1번 소를 1번이 아닌 다른 가고 싶은 축사 2번에 넣는다. 그 후 3번 소가 고를 차롄데 3번 소는 2번이 가고 싶다. 3번 소를 2번에 넣..

보기에는 간단한데 생각보다 난이도가 높은 문제이다. 가장 작은 수는 dp로, max는 그리디로 접근한다. #include #include int t, n; char max[102]; long long dp[101]; //성냥 개수 있을때 만들 수 있는 최대 수 char GreedyMax[8] = { 0x0,0x0,'1', '7', '4', '5','9','8' }; long long min[9] = { 0,0,1,7,4,2,0,8,10 }; void makeMax(int n,int idx) { if (n == 0) { return; } if (n % 2) { max[idx] = GreedyMax[3]; makeMax(n - 3, idx + 1); } else{ max[idx] = GreedyMax[2];..

네트워크를 직접 연결(!!)하는 아주아주 어려운 문제이다... 모든 컴퓨터가 직간접적으로 연결되어 있어야 하고 심지어 그 비용이 가장 적어야 한다.(속도는 상관 없나보다) 비용이 가장 적게 모든 노드를 연결하기만 하면 되므로 최소 신장 트리(MST: Minimum Spanning Tree)를 이용하여 트리 모양으로 고리가 생기지 않도록 연결해준다. (고리가 생기는 경우는 고리가 생기지 않는 경우보다 항상 비싸다) 우리는 MST 알고리즘 중 크루스칼 알고리즘(Kruskal's algorithm - Wikipedia)을 이용한다. 1. 가장 비용이 작은 간선부터 연결한다.(UNION FIND) 2. 같은 그룹에 속할 경우 연결하지 않는다. 간단한 그리디 알고리즘이다. 이 때 MST 가 항상 최소비용인 것은 ..

A -> B 로 가는 최소비용을 구하면 된다. A -> B 로 갈 수 있는 경우만 입력으로 주어진다는 조건이 있으므로 최소 비용 구하는 것만 신경쓰면 된다. 여기서 버스 비용은 0 이상이므로 버스를 이용할수록 손해이므로 버스는 최대 N-1 번 이용할 것이고, 한 번 타는데 최대 비용은 10^5 이고 N 은 10^3 이므로 최대 나올 수 있는 비용은 10^8 이므로 int 로 처리한다. #include #include #include #include using namespace std; int N, M, s, e, c; int start_city, end_city; vector edge[1001];//[도시번호] pair(비용,다음도시) int dijkstra(int start_city, int end_c..

1 end 라면 길이가 1인 수열이 제일 짧은 것이므로 종료해도 이상이 없다. len 은 N이 최대 10만이 나올 수 있으므로 초기값을 10만 + 1으로 잡고, 만약 더 짧은 것이 발견되지 않았다면 만들기 불가능한 경우이므로 0을 출력한다. 위의 풀이 방법으로 반드시 해를 찾을 수 있을까? s,e 를 index로 보고 start, end 를 가장 짧은 수열의 인덱스로 보자. 슬라이딩 윈도우의 상황을 여섯 가지로 볼 수 있을 것 같다. 1. s, e 가 모두 start 보다 작을 경우 2. s 가 start 보다 작고 e가 start 보다 같거나 크고 end 보다 작은 경우 3. s 가 start 보다 작고 e가 end 보다 같거나 큰 경우 4. s 가 start 보다 같거나 크고 e 가 end 보다 작은..

건물의 종류와 짓는 시간이 주어지고, 각 건물은 먼저 특정 건물이 지어지고 난 이후에나 지을 수 있다. 모든 건물 N개를 완성하는데 걸리는 최소 시간을 출력하면 되므로 일단 DP를 염두에 둘 수 있다. 명령을 내리고 일꾼이 이동하는 시간은 걸리지 않으므로 건물을 짓는 시간만 계산할 수 있고 건물마다 번호가 있으므로 간편하게 DP로 저장할 수 있을 것으로 기대한다. 여기서 두 번째 조건이 걸린다. 특정 건물이 지어지고 난 이후에나 지을 수 있는 건물들이 있는데, 여기서 문제에 나오지 않았지만, 여러 개의 건물이 필요한 경우가 있을 수도 있으므로 이런 경우에도 통과할 수 있도록 indegree를 센다. indegree는 자신에게 들어오는 경로의 개수를 의미하는데, 1, 2 번이 지어지고 난 이후 3번을 지을..