풀이 소요시간 : 60분 초과(실패)
백준 플랫폼의 실버 상위
, 골드 하위
문제와 프로그래머스 레벨2
문제 중 확실히 프로그래머스 문제가 어렵다고 느낀다. 유형 파악이 어렵고, 문제 풀이 방식이 비 정형적이다.
레벨 2 문제가 이정도로 까다롭게 느껴지는데, 아직 갈 길이 멀다고 느껴진다. 우선 카테고리를 DP
로 두긴 했지만, 풀이 과정이 다이나믹 프로그래밍이라고 보기에도 애매하다. 단지 Linear
하게 풀었다고 볼 수 있겠다.
D = 1,000,000 이다. O(N^2) 의 시간복잡도로는 절대적으로 풀이가 불가능하다.
따라서 Linear 하게 접근해야 함을 파악 할 수 있다. 내가 아는 Linear 한 풀이는 DP 뿐이기 때문에 이를 시도하였지만, 이전의 결과값을 다음 결과값에 포함시킬 이유가 전혀 없는 문제이기 때문에 DP 방식도 필요가 없음을 알 수 있었다.
비 정형적인 풀이를 요구하는 시점에서 멘탈이 조금 상했다.
D^2 와 X^2 의 값을 고정하고 Y^2 의 값을 튜닝해서 O(N) 의 시간복잡도로 문제를 풀 수 있다.
본인이 이런 방식을 떠올리지 못했다는 사실과, 비 정형적인 풀이 요구에 당황스러움이 겹친다.
접근 방식을 학습하고, 다음에 다시 나오면 맞춘다는 마인드를 강하게 가져야겠다.
그리고 DP 포함한 Linear 한 유형은 그냥 뇌 비우고 자료형은 long long
을 쓰도록 하자.
#include <string>
#include <cmath>
#include <vector>
using namespace std;
long long K;
long long D;
long long solution(int k, int d) {
K = k;
D = d;
long long Ans = 0;
for(long long X = 0; X <= D; X += K) {
Ans += (floor(sqrt(D*D - X*X) / K) + 1);
}
return Ans;
}