도지와 나

[백준] 7453.합이 0인 네 정수 (Swift) https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 풀이 1. 나눠서 풀기 크기가 최대 4000인 배열을 4개 이용해야 하기 때문에 완전탐색을 이용한다면 시간복잡도는 O(n^4) 이 되어 절대 테스트를 통과하지 못할 것입니다. 그래서 저는 4개의 배열을 두 개씩 묶기로 했습니다. 배열 A, B 에서 나올 수 있는 모든 수의 합, 배열 C, D 에서 나올 수 있는 모든 수의 합을 ..

[백준] 2467.용액 (Swift) https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 풀이 투포인터로 해결할 수 있는 문제입니다. 용액들의 값은 정렬된 상태로 주어지기 때문에 특성값이 0에 가까워지려면 더해지는 두 용액의 절대값의 차이가 작아야 합니다. 그렇기 때문에 초기 포인터는 양쪽 끝, 즉 최소값과 최대값을 가리키고 있어야 합니다. 2개의 포인터가 가리키는 값을 더한 다음 절대값을 씌워줍니다. 해당 값이 작을수록 0에 가깝다는 의미이..

[백준] 1484.다이어트 (Swift) https://www.acmicpc.net/problem/1484 1484번: 다이어트 성원이는 다이어트를 시도중이다. 성원이는 정말 정말 무겁기 때문에, 저울이 부셔졌다. 성원이의 힘겨운 다이어트 시도를 보고만 있던 엔토피아는 성원이에게 새로운 저울을 선물해 주었다. www.acmicpc.net 풀이 문제에서 나오는 G 는 (현재)^2 - (예전)^2 으로 표현할 수 있습니다. G 가 자연수이기도 하고 문제를 읽어보면 현재 몸무게가 예전 몸무게보다 값이 크다는 것을 알 수 있습니다. 문제의 조건을 만족하는 모든 경우의 수를 출력해야하기 때문에 예전 몸무게를 1, 현재 몸무게를 2라고 생각하고 차례차례 탐색해보겠습니다. (현재)^2 - (예전)^2 라는 식을 조건..