프로그래머스 - 멀쩡한 사각형

▶ 문제 설명

[ 문제 ] 

가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다. 새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다.
가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요.

 

[ 제한사항 ]

• W, H : 1억 이하의 자연수

[ 입출력 예 ]

W	H	result
8	12	80

[ 입출력 예 설명 ]

 

입출력 예 #1
가로가 8, 세로가 12인 직사각형을 대각선 방향으로 자르면 총 16개 정사각형을 사용할 수 없게 됩니다.

원래 직사각형에서는 96개의 정사각형을 만들 수 있었으므로, 96 - 16 = 80 을 반환합니다.

 

---

 

[ 나의 답변 ] 

 

이번문제는 굉장히 애를 많이 먹은 문제였습니다.

문제 풀이 자체는 간단히 풀었는데, 1억이하의 자연수에서 여러 번 테스트를 통과하지 못했습니다.

 

int형으로 width와 height가 주어지는데, 처음에 꼭 필요한 과정 중 하나는 width와 height로 총 멀쩡한 사각형을 구하는 것 입니다. 

 

long long answer = width * height;

처음에 이렇게 실수를 했습니다...

 

int가 가질 수 있는 정수의 범위는 -2147483648 ~ +2147483647 이고,

signed long long 이 가질 수 있는 정수의 범위는 -9223372036854775808 ~ +9223372036854775807 이고,

unsigned long long 이 가질 수 있는 정수의 범위는 0 ~ 18446744073709551615 입니다.

 

int형과 int형을 곱하면 int형이 나오는데, 1억이하의 자연수라는 조건이 붙었기 때문에 int형으로 곱한값이 나오면 값이 짤리게 되어 정상적으로 나오지 않게 됩니다.

 

 

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
using namespace std;

long double graph(long long w, long long h, long long y)
{
	return (long double)(h - y) * ((long double)w / (long double)h);

}

long long solution(int width,  int height)
{
	long long answer = (long long)width * (long long)height;

	long long min = 0;
	long long max = 0;

	for (int y = height - 1; 0 <= y; --y)
	{
		long double val = graph(width, height, y);
		long long a = (long long)ceil(val);
		answer -= (a - min);

		min = floor(val);
	}

	return answer;
}