https://www.acmicpc.net/problem/15686 치킨집 중에서 M개를 고르는 모든 조합을 만든 후 각각의 집을 가장 가까운 치킨집에 연결시킨다. 모든 경우 중 최소값이 답이다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include #include #include #include #define INF 987654321using namespace std; int n,m,t,lenh,lenc,ans=INF;vector h,c; int dist(pair a,pair b){ return abs(a.first-b.first)+abs(a.second-b.second);} int main(){..
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBJAVpqrzQDFAWr d[i][j] = 가방의 크기가 i일 때 j번째 물건까지 담을 수 있는 최대 가치 1. 가방의 크기가 i일 때 j번째 물건을 담을 수 있다면 j번째 물건을 담는 경우와 아닌 경우 중 최대값으로 채운다. d[i][j] = max(d[i][j-1],d[i-v[j]][j-1]+c[j]) 2. 가방의 크기가 i일 때 j번째 물건을 담을 수 없다면 j-1번째 물건까지 담을 수 있는 최대 가치로 채운다. d[i][j] = d[i][j-1] 1234567891011121314151617181920212223242526#include #include u..
https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBC1lOad9IDFAWr 수가 최대 100자리수까지 될 수 있으므로 일반적인 자료형으로는 덧셈을 할 수 없다. string으로 두 수를 받은 후 자릿수를 맞춰준 후 덧셈을 구현한다. 1234567891011121314151617181920212223242526272829#include #include #include using namespace std; int main(){ int t; scanf("%d",&t); for(int k=1;k>a>>b; int n=a.size(),m=b.size(),len=max(n,m); if(n>m) for(int i=0;..
https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBOHEx66kIDFAWr d[i][j] = 첫번째 문자열의 i번째까지의 부분 문자열과 두번째 문자열의 j번째 부분 문자열의 최대 공통 부분 수열의 길이 편의상 d 배열의 0번째 행이나 열은 0으로 초기화해두고 (1,1)부터 채워 나간다. 1. a[i]와 b[j]가 같은 경우마지막을 제외한 각각의 문자열의 최대 공통 부분 수열의 길이에 1을 더하면 되므로 d[i][j]=d[i-1][j-1]+1이다. 2. a[i]와 b[j]가 다른 경우a의 마지막을 제외하고 b와 비교한 경우, b의 마지막을 제외하고 a와 비교한 경우 중 최대값을 d[i][j]에 넣으면 된다...
https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBOKg-a6l0DFAWr d[i] = a[i]를 마지막으로 하는 최장 증가 부분 수열의 최대 길이 자기 자신이 부분 수열이 될 수 있으므로 d 배열의 초기값을 1로 둔다. d[i]은 j=0~i-1까지 보면서 a[j]d[i]인 경우 d[i]을 d[j]+1로 갱신한다. O(N^2)으로 테이블을 모두 채울 수 있다. 12345678910111213141516171819202122#include #include using namespace std; int t,n,a[1000],d[1000],ans; int main(){ scanf("%d",&t); for(int ..
https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWHz7xD6A20DFAVB&categoryId=AWHz7xD6A20DFAVB&categoryType=CODE 한자리수 만들고 한자리수 중에 체크 안된것 확인 -> 두자리수 만들고 두자리수 중에 체크 안된것 확인 ... 체크 안된 수를 찾을 때 까지 반복한다. 체크 배열을 세자리수까지만 잡았는데 세자리 안에 답이 나오는 것 같다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include #include int t,n,a[1000],c[1000]; int po..
https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7IzvG6EksDFAXB#none 재귀로 모든 조합을 만들어 본다. 조합을 만드는 도중 합이 K를 넘어가면 더 이상 만들지 않는다. 1234567891011121314151617181920212223242526272829#include int t,n,k,a[20],ans; void go(int i,int sum){ if(sum>k || i==n) { if(sum==k) ans++; return; } go(i+1,sum+a[i]); go(i+1,sum);} int main(){ scanf("%d",&t); for(int T=1;T
https://www.acmicpc.net/problem/14891 K번 톱니바퀴를 회전시킨 후 점수의 합을 구하는 문제이다. 매번 톱니바퀴를 돌리면 서로 맞닿은 극이 다를 경우에만 회전하게 된다. 현재 상태를 기준으로 다음 회전할 방향을 미리 저장한 후 move함수를 이용하여 상태를 변화시킨다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091#include #include // w[i][j]: i번째 톱니바퀴의 j번째 점수// nd[i]: i번..
https://www.acmicpc.net/problem/14890 모든 행과 열의 인접한 경사들을 살펴보면서 경사의 차이가 1일 때, 앞이 더 큰 경우와 뒤가 더 큰 경우가 있다. 각각의 경우에 대하여 경사가 낮은쪽으로 길이가 L인 경사로를 놓을 수 있는지 확인한다. 확인하는 과정에서 인덱스가 범위를 넘어가거나 경사가 달라지거나 이미 경사로가 있다면, 해당 행 또는 열에는 경사로를 놓을 수 없다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091..
https://www.acmicpc.net/problem/14889 팀을 절반씩 나누는 모든 경우를 만들어서 능력치의 차이를 계산해본다. 최대 20C10 = 184756 이므로 시간 내에 충분히 수행될 수 있음을 알 수 있다. 12345678910111213141516171819202122232425262728293031#include #include #include #include #define INF 987654321using namespace std; int n,a[20][20],v[20],ans=INF; void solve(){ vector start,link; for(int i=0;i