(백준 1484번 다이어트) 라이님 블로그 대회 알고리즘 따라잡기 14) 투 포인터, 슬라이딩 윈도우

오늘은 백준 1484번 다이어트 문제를 풀어보았다. 처음에 푼 방법부터 발전시켜서 시간과 메모리를 아주 많이 단축했다!!

 

백준 1484번

https://www.acmicpc.net/problem/1484

 

 

첫번째 풀이

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <vector>
using namespace std;
constexpr int MAX = 10000000;
// int 범위 +- 2*10^9
// long long 범위 +- 9 * 10^18
int main() {
	int N; scanf("%d", &N);
	vector<long long> v;
	v.resize(MAX+1);
	for (int i = 0; i < MAX+1; i++) v[i] = (long long) i * i;

	vector<int> weight;
	int s = 1, e = 1; long long diff = 0;
	while (1) {
		// e++
		if (diff <= N) {
			diff -= v[e++];
			diff += v[e];
		}
		else if (e == MAX - 1) break;
		else {
			diff += v[s++];
			diff -= v[s];
		}
		if (diff == N) weight.push_back(e);
	}
	if (weight.empty()) printf("-1");
	for (int w : weight) {
		printf("%d\n", w);
	}

	return 0;
}

이 풀이에서의 문제점 : 

1. i의 제곱을 저장해놓고 사용 → 바로바로 계산해서 사용하기

2. weight에 push_back해서 저장 → 바로바로 printf하기

 

두번째 풀이 

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <vector>
using namespace std;
constexpr int MAX = 10000000;
// int 범위 +- 2*10^9
// long long 범위 +- 9 * 10^18
int main() {
	int N; scanf("%d", &N);
	
	vector<int> weight;
	int s = 1, e = 1; long long diff = 0;
	while (1) {
		// e++
		if (diff <= N) {
			diff -= (long long) e * e; e++;
			diff += (long long) e * e;
		}
		else if (e == MAX - 1) break;
		else {
			diff += (long long) s * s; s++;
			diff -= (long long) s * s;
		}
		if (diff == N) weight.push_back(e);
	}
	if (weight.empty()) printf("-1");
	for (int w : weight) {
		printf("%d\n", w);
	}

	return 0;
}

이 풀이에서의 문제점 : 

1. while문 탈출조건!! e = s + 1이고 diff > N인 경우 탈출 가능

(e^2 - s^2 = 2s + 1 > N인 경우 s를 아무리 늘려도 diff가 작아질 수 없기 때문!)

 

내가 생각한 정답 풀이

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <vector>
using namespace std;
constexpr int MAX = 10000000;

int main() {
    int N; scanf("%d", &N);

    int cnt = 0;
    int s = 1, e = 1; 

    while (1) {
        long long diff = (long long)e * e - (long long)s * s;
        if (e == s + 1 && diff > N) break; // 조기 종료 조건
        else if (diff > N) s++;
        else if (diff < N) e++;
        if (diff == N) {
            printf("%d \n", e);
            cnt++;
            s++;
        }
    }
    if (cnt == 0) printf("-1\n");

    return 0;
}