https://www.acmicpc.net/problem/1484 1484번: 다이어트 성원이는 다이어트를 시도중이다. 성원이는 정말 정말 무겁기 때문에, 저울이 부셔졌다. 성원이의 힘겨운 다이어트 시도를 보고만 있던 엔토피아는 성원이에게 새로운 저울을 선물해 주었다. www.acmicpc.net 수학과 투 포인터 문제다. 성원이의 몸무게가 G 킬로그램 늘었다. 이 G킬로그램은 현재 몸무게의 제곱에서 성원이가 기억하고 있던 몸무게의 제곱을 뺀 것이다. 입력은 자연수로 들어오므로 모든 몸무게는 자연수다. 처음 생각한 방법은 어떤 수의 제곱에서 g를 뺀 수도 제곱수라는 점을 활용하는 것이다. 반복문으로 1부터 g까지 순회하면서 해당 수의 제곱에서 g를 빼고 그 수(tmp)가 제곱수 인지 확인했다. tmp가 ..
Algorithm/Two Pointer
https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 투 포인터와 누적 합 문제다. 주어진 배열에서 연속된 수들의 부분합 중에 s이상이 되는 수열 중, 가장 짧은 것의 길이를 구하는 문제다. 투 포인터를 사용하여 앞에서부터 포인터를 옮겨주며 해당 포인터들 사이의 누적 합 연산을 수행했다. 합이 s 미만이면 right 포인터를 한 칸 옮겨주어 합을 늘렸다. right 포인터가 끝에 다달았다면 반복문을 종료했다. (누적 합이 더 커질 수 ..
https://www.acmicpc.net/problem/13144 13144번: List of Unique Numbers 길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라. www.acmicpc.net 투 포인터 문제다. 중복이 없는 수열의 시작과 끝 + 1을 투 포인터로 찾으려고 했다. 1 2 3 4 1 2 의 경우 start = 0, end = 4까지 연산을 거치고 이 때 1 / 1, 2 / 1, 2, 3 / 1, 2, 3, 4의 4가지 수열이 나온다. 2, 3 / 2, 3, 4 / 3, 4 등도 존재하지만 중복 계산을 방지하기 위해 start의 값을 포함하는 수열만을 계산했다. 방법은 금방 찾아냈..
