본문 바로가기

Coding

 (195)
9251번 LCS 다이나믹 프로그래밍. 예시로 나온 ACAYKP, CAPCAK으로 설명해보자. 첫번째 문자열 시작점을 기준으로 하나씩 비교해서 LCS 길이를 구하게 되면 시간을 초과하게 된다. (이중 for문) 따라서 DP로 해결하면 된다. A C A Y K P C 0 A 1 P 1 C 1 A 1 K 1 A를 기준으로 생각해보자. 1. C를 만났을때 같지 않으므로 0 2. A를 만났을때 같으므로 1 3. P를 만났을때 같지 않으므로 0이지만 그 전에 A를 만났으므로 최대값 1 4. C를 만났을때도 마찬가지 1 5. A를 만났을때 같으므로 1 6. K를 만났을때 최대값 1 A C A Y K P C 0 1 A 1 1 P 1 1 C 1 2 A 1 2 K 1 2 C를 기준으로 생각해보자. 1. C를 만났을때 같으므로 1 2. A..
1541번 잃어버린 괄호 '-'가 나올때까지 더하다가 '-'가 나온 순간부터 값들을 모조리 빼주면 된다. 12345678910111213141516171819202122232425262728293031323334353637#include #include using namespace std; string str;string num;int ans;bool plmi=true; void solved(){ for(int i=0;i> str; solved(); cout
2798번 블랙잭 브루트포스 문제. 3개씩 골라서 더한 값이 'M값 이하 + 제일 큰' 값을 찾으면 된다. **6603번 로또 참고, https://www.acmicpc.net/problem/6603 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 38 39 #include #include using namespace std; int N,M; int num; int answer; vector vec; void solved(int start, int cnt, int num, int sum){ if(cnt==3){ if(sum N >> M; for(int i=0;i> k; vec.push_ba..
6603번 로또 재귀 문제. 시작점을 기준으로 6개씩 고르면 된다. 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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 #include #include #include using namespace std; queue LottoK; queue LottoS; vector vec; int K,S; int answer[6]; void solved(int num, int start, int cnt){ if(cnt==6){ for(int i=0;i
4963번 섬의 개수 BFS 기본 문제. 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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 #include #include #include #define visited true #define Non_visited false #define MAX 51 using namespace std; typedef pa..
2966번 찍기 브루트 포스 기본 문제. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include #include #define MAX 101 using namespace std; char Adrian[3]={'A','B','C'};char Bruno[4]={'B','A','B','C'};char Goran[6]={'C','C','A','A','B','B'};int N;int A,B,C;int answer;char P[MAX]; int main(){ cin >> N; for(int i=0;i> P[i]; } for(int i=0;i
2858번 기숙사 바닥 브루트 포스 기본 문제. 이지만 수학적으로 풀었다. 1. 안에 들어가는 갈색 타일을 생각해보자. 정수로밖에 나눌 수 없기 때문에 갈색 타일의 약수로 떨어져야한다. Ex) 갈색 타일이 4개 일 경우 1*4, 2*2, 4*1 즉, 경우의 수 3가지가 나올 것이다. (하지만 4*1과 1*4는 똑같으므로 절반까지만 구하면 된다) 2. x축, y축을 생각해보자. 갈색 타일을 기준으로 x+2, y+2를 한 뒤 곱한 값(넓이)은 (갈색 타일 + 빨간색 타일)의 값이 되어야 한다. 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 38 39 40 41 42 43 44 45 46 #incl..
1748번 수 이어 쓰기 1 브루트 포스 기본 문제. Ex) 1200 1~9 -> 9*1 10~99 -> 90*2 100~999 -> 900*3 ...... ... .. 1000~1200 -> (1200-1000+1)*4 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 using namespace std; string N; long answer; int main(){ cin >> N; long size = N.size()-1; long k=1; long num=stoi(N); for(int i=1;i

티스토리툴바