답은 알고리즘 뿐이야!

문제 출처 : https://www.acmicpc.net/problem/1062 풀이 : 백트래킹 문제입니다. "anta"와 "tica"는 무조건 포함 되니 알파벳 'a','n','t','i','c' 는 무조건 배워야 합니다. 따라서 k가 5 미만이면 모든 단어를 읽을 수 없습니다. 이를 이용해 알파벳 'a','n','t','i','c'는 무조건 포함된다고 판단하고 5개를 제외한 알파벳 중 k-5개를 뽑는 문제가 되겠습니다. 알파벳의 순서는 상관없으니 오름차순으로 뽑아주어 시간을 단축할 수 있습니다. 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 4..

문제 출처 : https://www.acmicpc.net/problem/7453 풀이 : 네 정수의 합을 0으로 만드는 문제입니다. 이 문제는 [BOJ 16287] Parcel (ICPC 2018) 과 비슷한 개념을 사용하여 풀면 됩니다. a,b의 합을 ab라는 배열로 묶고, c,d의 합을 cd라는 배열로 묶어서 각각 정렬한다음 ab를 기준으로 cd중 -ab와 같은 값을 이분탐색을 통해 찾으면 됩니다. 저는 어퍼바운드를 구현하여 끝에서부터 내려오면서 중복 체크를했습니다. ab의 값이 같다면 계산을 생략해주어야 시간초과가 나지 않습니다. 해쉬로도 풀수있는거 같으니 다음에 한번 풀어보겠습니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 2..

문제 출처 : https://www.acmicpc.net/problem/1644 풀이 : 소수문제입니다. 소수는 항상 에라토스테네스의 체를 사용하시면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include int n,arr[4000001],s[300000],cnt,ret,sum; int main() { scanf("%d", &n); for (int i = 2; i = 0&&sum

문제 출처 : https://www.acmicpc.net/problem/2661 풀이 : 백트래킹 문제입니다. 1,2,3 중 하나의 수로 들어가는데 들어가기전에 맨 뒤에서 부터 한개씩 두개씩 ~ 확장하면서 같은 부분 수열이 있는지 유망성 검사를 해주고 들어가시면 됩니다. 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 #include int n,arr[81],type; bool backtracking(int itr) { if (itr > n)return true; for (int i = 1; i

문제 출처 : https://www.acmicpc.net/problem/1932 풀이 : DP 문제입니다. 저는 위의 두개의 값을 비교하여 채워나가는 형식으로 짰습니다. 왼쪽과 오른쪽의 값중 큰것을 선택하여 그 셀에 합쳐 나가시면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 #include #define max(A,B) ((A)>(B)?(A):(B)) int n, arr[500][500],ret,l,r; int main() { scanf("%d", &n); for (int i = 0; i

문제 출처 : https://www.acmicpc.net/problem/2644 풀이 : 두 사람 사이의 촌수를 계산하는 문제입니다. 이는 두 사람 사이에 엣지가 몇개 있는지를 묻는 문제로 지나간 엣지 갯수를 저장해주면서 탐색하시면 됩니다. 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 #include #include using namespace std; queueq; pair p; int n, s, e, map[101][101], check[101], a, b, k; int main() { scanf("%d\n%d %d\n%d", &n, &s, &e, &k); while (k--) { sc..

문제 출처 : https://www.acmicpc.net/problem/8902 풀이 : 2차원 DP문제입니다. 두개의 라인이 존재하는데 각라인에서 몇대가 합류했는지를 DP로 쌓으시면 됩니다. 저는 cache[line1][line2]의 형태로 저장했습니다. 문제에서 원하는 결과값은 결국 모든 끝나는 지점에서 모든 시작지점을 뺀 값과 같습니다 따라서 cache를 쌓을때 각 색깔별로 맨처음과 맨끝이 어디있는지를 비교하여 1. 그 색깔에서 맨 처음 나왔을 경우 : 그 위치를 (-) 해줌 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 2..

문제 출처 : https://www.acmicpc.net/problem/9095 풀이 : DP문제입니다. 1, 2, 3으로 새로운 방법을 만들 수 있는 경우는 i-1인 경우 : + '1' i-2인 경우 : + '2' i-3인 경우 : + '3' 이 세가지 경우 입니다. 따라서, cache[i] = cache[i-1]+cache[i-2]+cache[i-3]대로 쌓으면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 #include int t,n,cache[11]; int main() { scanf("%d", &t); cache[1] = 1, cache[2] = 2,cache[3] =4; for (int i = 4; i

문제 출처 : https://www.acmicpc.net/problem/17521 풀이 : 2019 ICPC 예선문제입니다. 모든 정보를 알기 때문에 최대의 이익을 뽑아내기 위해서는 항상 저점 매입해서 고점에서 매도하면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include int n, arr[16], ma, mi; long long int k; int main() { scanf("%d %lld", &n, &k); for (int i = 0; i

문제 출처 : https://www.acmicpc.net/problem/16287 풀이 : 4개의 무게의 합이 w가 되는 조합이 있는지 물어보는 문제입니다. 단순하게 생각하면 nC4로 4중포문을 도는 방법을 생각 할 수 있겠지만, 이방법은 N이 5000이니 거의 불가능 하다고 판단이 됩니다. 그러므로 one + two + three + four = w 의 형식을 살짝 바꿔서 one + two = w - three - four 의 형식으로 바꿉니다. 그러면 one + two를 구하는 문제로 바뀌게 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #include int w, n, arr[5000], wei[800000]; int main()..