안 쓰던 블로그

www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 처음 풀이-dp #include #include #include using namespace std; int dp[100001], coin[2] = { 2,5 }, n; int f(int v) { if (v 0) return dp[v]; int res = 1e9; for (int i = 0; i < 2; i++) { res = min(res, f(v - coin[i]) + 1); dp[v] = res; } return res; } int m..

www.acmicpc.net/problem/15721 1) 뻔 – 데기 – 뻔 – 데기 – 뻔 – 뻔 – 데기 – 데기 뻔 – 데기 – 뻔 - 데기 – 뻔 – 뻔 – 뻔 – 데기 – 데기 – 데기 뻔 – 데기 – 뻔 - 데기 – 뻔 – 뻔 – 뻔 - 뻔 – 데기 – 데기 – 데기 - 데기 ... 한 바퀴 돌 때마다 이런 식으로 뻔과 데기가 늘어난다 2) 만약 사람이 7명이고 16번째 뻔을 말한 사람을 구하려면 입력은 7 16 0이고 뻔 데기 뻔 데기 뻔 뻔 데기 데기 뻔 데기 뻔 데기 뻔 뻔 뻔 데기 데기 데기 뻔 데기 뻔 데기 뻔 뻔 뻔 뻔 데기 데기 데기 데기 뻔 이니까 2번째 사람이 16번째 뻔을 말했으니 2를 출력한다 사람은 0부터 센다 3) 사람이 1명일 수도 있다 1명이면 혼자서 뻔 데기를 다..

17408 수열과 쿼리24 최대값의 위치를 구하는 문제 각 구간의 최대값을 저장한 세그먼트 트리를 만들어서 쿼리를 처리해 주기만 하면 된다 업데이트나 트리 값을 바꿀 때 그냥 리턴하지 않고 임시로 값을 저장해 두고 앞쪽 쿼리, 뒷쪽 쿼리 값을 비교해서 최대값을 갱신하는 식으로 구현했다 근데.. 아래 코드에서 5 5 4 3 9 5 1 2 3 5 하면 14가 나와야 하는데 왜 12가 나오는지 알 수가 없다ㅜ 2 4 5 하면 14가 나오는 거 보면 3-9-5부분이 갱신이 안 된 듯한데 아무리 코드를 봐도 왜 저기만 업데이트가 안 되는지 모르겠다.. 너무 안 풀려서 일단 코드 올리고 패스 https://github.com/proqk/Algorithm/blob/master/Segment%20Tree/17408%2..

https://www.acmicpc.net/problem/1699 어떤 수 n을 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 문제 처음 접근 방식 1. 무식하게 접근 n=11이라고 했을 때 for문 하나를 돌면서 n보다 작으면서 가장 큰 제곱수 k를 찾는다 3^2=9니까 k=3 while문을 n>0이고 k!=0일 때까지 돌면서 n에서 k^2을 뺄 수 있을 때까지 뺀다 뺄 수 없다면 k--로 넘어간다 이 방법을 재귀로 바꾼다 2. 재귀로 완전 탐색 이런 식으로 돌면서 cnt로 항을 세면 됐다 이 재귀를 DP로 바꾼다 3. DP로 변환 근데 여기서 막혔다 로직은 k가 1부터 올라가면서, m에 합을 저장하고 dp[k][m]은 합이 m일 때의 항의 최소 개수로 뒀다 (그림에서는 a가 있지만 잘못씀)..

교내대회에서 멘탈공격맞고 K.O 브론즈~실버나 돌아야겠다 17362 수학은 체육과목입니다2 1 2 3 4 5 6 7 8까지 하면 한 사이클을 도니까 8로 나눌 건데 수를 직접 써보면 알겠지만 14 15 16같이 오른쪽에서 왼쪽으로 넘어가는 수는 나머지가 1~5로 나오지 않음 그 경우만 예외로 해주면 된다 6이 나오면 4 출력, 7이면 3출력, 8이면 8로 나누고 있어서 나머지가 0이니까 나머지가 0일때는 2출력 10757 큰 수 A+B 파이썬으로 하면 그냥 출력하면 된다 갓-언어 C++로 보면 처음 딱 봤을 때는 string으로 a b를 받고 한 자리씩 int형으로 변환해서 더해주는데 만약 올림이 있다면 carry변수에 저장 해서 다음 자리의 sum을 구할 때 1을 더 더한다 라고 생각했음 근데 더 간단..

https://www.acmicpc.net/problem/7578 7578번: 공장 어떤 공장에는 2N개의 기계가 2열에 걸쳐 N개씩 배치되어 있다. 이 2개의 열을 각각 A열과 B 열이라고 부른다. A열에 있는 N개의 기계는 각각이 B열에 있는 N개의 기계와 하나씩 짝을 이루어 케이블� www.acmicpc.net 예제 그림을 보면 교차하는 부분은 3곳 교차하는 지점의 특징: 똑같은 132가 있어도 A에서의 위치와 B에서의 위치가 다르다 A[i]를 A에서 i의 위치, B[i]를 B에서 i의 위치라고 치면, A[i]B[j] 조건이 성립하면 접점 1개가 생긴다고 할 수 있다 그냥 반복문으로 단순 구현하면 A를 i로 돌면서 j로 조건에 맞는 수가 있는지 찾는 2중for문이 되고 O(n^2)의 시간복잡도로 5..

오늘은 세그트리 달린다 https://www.acmicpc.net/blog/view/9 세그먼트 트리 (Segment Tree) 문제 배열 A가 있고, 여기서 다음과 같은 두 연산을 수행해야하는 문제를 생각해봅시다. 구간 l, r (l ≤ r)이 주어졌을 때, A[l] + A[l+1] + ... + A[r-1] + A[r]을 구해서 출력하기 i번째 수를 v로 바꾸기. A[i www.acmicpc.net 최대/최소값 찾기 12015 가장 긴 증가하는 부분 수열2 tree[i] = 수 A[i]를 마지막으로 하는 LIS의 길이로 두면, 1) i보다 앞에 있으면서(j