답은 알고리즘 뿐이야!

문제 출처 : https://www.acmicpc.net/problem/1103 풀이 : DFS 문제입니다. BFS로 풀게되면 이전에 온 경로를 알 수 없으므로 DFS를 사용하여 풀어야 합니다. DFS로 현재까지 온 경로를 체크하면서 오면 중복해서 가는 지점을 찾을 수 있어 무한대로 움직이는 경우를 찾을 수 있습니다. 그리고 시간 단축을 위해 메모이제이션 개념을 사용해 그 지점에 도착했을때 현재 이동한 횟수가 이전에 그 지점에 도달했을때의 횟수보다 작다면 스킵해줍니다. 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 #include int n, m, ret, visit[50][50], cache[5..

문제 출처 : 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..