[Programmers] 점 찍기(LV.2)

Alice·2023년 5월 24일
0

풀이 소요시간 : 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;
}
profile
SSAFY 11th

0개의 댓글