취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 11561번 문제인 징검다리이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/11561

N이 어떤 수가 오더라도, 징검다리를 주어진 규칙에 맞게 최대한 많이 밟아 건너는 방법 중 하나는 greedy하게 처음서부터 1칸, 2칸, 3칸, ... , n칸과 같이 최대한 적은 칸씩 징검다리를 건너뛰는 것임을 생각할 수 있다. 특히, 마지막 N번째 칸은 꼭 밟아야하므로, X번 칸까지 밟은 뒤에 N번칸으로 뛸 수 없다면 그 X번 칸으로 뛴 점프를 N번 칸으로 바꾸는 점프로 바꿔주는 것으로 최대한 징검다리를 많이 밟아 건너는 경우의 수 중 하나를 찾을 수 있다.

1부터 n까지의 간격의 점프를 한번씩 모두 하여 이동한다면 총 n(n+1)/2칸을 이동하게 되고, n+1까지의 간격의 점프를 한번씩 모두 하여 이동한다면 총 (n+1)(n+2)/2칸을 이동하게 된다.

따라서, 주어진 N에 대하여 n(n+1)/2 <= N < (n+1)(n+2)/2 를 만족하는 N을 찾으면 된다.

이는 각 항에 2를 곱하고 정리하여 간단히 구할 수 있다. 그 이유는 각 항에 2를 곱해 얻은 2N의 범위에서는 제곱수가 (n+1)^2 정확히 하나만 존재하기 때문이다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <cmath>
using namespace std;

long long arr[231];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int T; cin >> T;
	while (T--) {
		long long N; cin >> N;
		long long ans = sqrt(2 * N);
		if ((ans * ans + ans) / 2 <= N) cout << ans << '\n';
		else cout << ans - 1 << '\n';
	}
}