https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15StKqAQkCFAYD 가능한 간선을 모두 저장한 후 MST를 만든다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include #include #include typedef long long ll;using namespace std; struct Edge{ ll start,end,cost; bool operator
https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LwsHaD1MDFAXc 먼저 모든 칸의 주변 8방향의 지뢰의 갯수를 표시한다. 그리고 0인 칸을 따로 담는다. BFS로 0이 포함된 영역과 가장자리 숫자까지를 하나로 세준다. 마지막으로 남은 숫자들을 더해주면 최소 횟수가 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869#include #include #include using namespace std; int t,n,..
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWO6cgzKOIEDFAWw&categoryId=AWO6cgzKOIEDFAWw&categoryType=CODE 숫자 4를 사용하지 못하므로 기존의 10진법에서 4를 하나 뺀 9진법으로 생각하자. 4 이상의 숫자들을 하나씩 줄여준 다음 10진법으로 바꾼다. 0층이 없으므로 부호에 따라 계산에 유의하자. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 #include typedef long long ll; ll cvt(char *a,ll ..
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.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV134DPqAA8CFAYh 좌우로 거리가 2씩 조망권이 보장되는 세대수를 세는 문제이다. 일단 기준이 되는 건물의 높이가 좌우로 거리가 2 안에 들어오는 건물보다 높아야 한다. 그렇다면 조망권이 보장되는 세대수는 현재 건물의 높이에서 좌우로 2개씩 총 4개의 건물 중 가장 높은 건물의 차이이다. 12345678910111213141516171819202122#include #include using namespace std; int main(){ for(int k=1;k