[프로그래머스] 멀쩡한 사각형 (일차함수 & 자료형)

이 글에서는 프로그래머스 -멀쩡한 사각형 문제에 대해 다뤄보겠습니다. 문제 풀이는 C++로 이루어져 있고 함께 들어가 있는 개념들도 간단히 정리 해보는 형식으로 작성되었으므로 오타등의 오류가 있을 수 있습니다. 오류 발견시 댓글로 꼭 말씀해주세요! 시작해볼까요?

 

저는 문제를 풀고나서 꼭 구글에 해당 문제를 한 번 검색을 해 봅니다.

다른 사람들의 풀이가 도움이 된다고 해서 검색은 해보지만 다수와 다르게 풀었다면 골치가 조금 아픕니다.

대중적인 풀이(?)가 더 효율성이 좋은건가... 하고 효율성도 따져야 하고...

아직 이 문제에 대해서 효율성 검사를 해보지는 않았지만 이 글 쓰고 해보겠습니다.

이 문제를 풀 때 많이 쓰시는 방법이 gcd (최대공약수)를 사용하시던데 아직 찬찬히 살펴보지 않아 어떤 맥락에서 최대공약수를 쓰는지는 잘 모르겠습니다. 저는 일차함수, 올림, 대칭 이렇게 3가지 원리를 사용해서 풀도록 하겠습니다.

풀이 1

아래 [그림 1]이 많은 설명을 하고 있으니 글을 읽기 싫으신 분들은 아래 그림만 찬찬히 살펴보셔도 괜찮을 것 같습니다.

문제의 예시로는 w = 8, h = 12 였고 대각선이 반대로 그어져 있지만 중요한 요소가 아니므로 내가 보기 좋게 제 1, 3 사분면을 가로지르게끔 바꿉시다. 그러면 2가지 특징을 잡을 수 있습니다.

1. 대각선을 기준으로 멀쩡한 정사각형들은 대칭으로 포진되어 있음

2. 대각선 위쪽의 정사각형은 y 값을 올림한 값 부터 시작함

 

[그림 1]을 참고하신다면 더 잘 이해가 되실 것 같습니다. 예를 들어 x = 3 일때의 y 값은 4.5입니다.

그러므로 멀쩡한 정사각형들은 5번째 블록부터 12번째 블록까지입니다. 여기에 대칭인 사실을 이용하면, x = 6인 지점의 아랫부분이 7개의 블록이 멀쩡한 블록입니다.

[그림 1]

원리는 방금 말씀드린 것과 같이 생각하시고 푸시면 됩니다. 단, 이 문제의 또다른 함정은 바로 자료형에 있습니다.

제가 이전에 <자료형 무시하지 마라>라는 포스트를 올렸었는데 한 번 범위를 다시 확인해보시면 좋을 듯 합니다.

이 문제에서 가로와 세로는 1억 이하의 자연수라고 합니다. w와 h 값을 받을 때는 1억 이하니 int로 받을 수 있지만 블록 수를 계산할 때는

충분히 int 범위를 넘을 수 있습니다. 그러므로 형변환에도 주의해야 합니다.

제가 형 변환 인지를 하지 않고 문제를 풀지 않았을 때 12~17번 케이스에서 실패가 떴으니 혹시 12~17번 케이스가 왜 안되는지 고민하시는 분들은 자료형 문제라고 생각하시면 됩니다. 

 

코드를 복사해서 쓰시고 싶으신 분들은 아래 더보기를 눌러주시면 됩니다,

#include <cmath>

using namespace std;

long long solution(int w, int h) {
    long long answer = 0;

    // func : y = h/w x
    // use the fact that it's symmetric
    for(int i = 1; i <= w; i++){
        double pos = ceil((long long)h * i / (double)w);
        int block = h - pos;
        
        answer += block;
    }
    
    answer = answer * 2;
    return answer;
}

#2 : 올림 계산을 위해 ceil을 사용하는데 ceil()은 <cmath>에 포함되어 있습니다.

#10 : (long long)h로 쓴 이유는 곱셈과 나눗셈이 일어날 때 h의 자료형을 따를 것이므로 h의 자료형을 그에 맞춰 놓아야 합니다, 또한 h와 w가 선언이 int로 되어있기 때문에 (double)w를 하지 않으면 알아서 int로 형을 바꾸므로 반드시 (double)w를 해주어야 합니다.

#11 : 대각선 위쪽 블록들을 계산해서 더합니다.

#16 : 대각선 위 아래가 대칭이므로 아래 쪽까지 구해야 하므로 구한 답에 2배를 해줍니다.