두 원 사이의 정수 쌍(V)

문제: https://school.programmers.co.kr/learn/courses/30/lessons/181187

프로그래머스

 

문제설명 : 내원과 외원 사이의 점들의 갯수를 구해야한다.

사이에서의 각 픽셀(rectangle)이 내원이나 외원에 접하는 경우 (하기 그림, x =3 일때) 도 카운팅한다.

 

(그림 출처 : https://sasca37.tistory.com/320)

 

TC

r1	r2	Return
2	4	40
9	20	1008
10	20	952
999999	1000000	6281440
3	4	24
1	2	12

 

로직:

1. 사분표로 되있기에 1사분표의 갯수만 구하여서 1사분표 점 갯수 *4 할 것이다.

▶ 피타고라스 정리 x^2 + y^2 = r^2 을 활용한다.  => y^2 = r^2 - x^2;
▶ 주어지는 x, r에 의해 y 좌표를 알 수 있다. (y의 좌표는 픽셀 상단 우측 꼭짓점 기준으로 한다.)
▶ 구해진 y좌표가 소수점인 경우 외원은 내림으로 내원은 올림을 한다. 

▶ r1_y <= t <= r2_y 범위에서 t의 갯수를 구한다. => cnt = r2_y - r1_y + 1
   => 동적으로 최대 1,000,000 사이즈를 갖는 벡터를 만들면 기억공간이 많이 든다.[내원의 경우 원을 초과하는 x좌표의 y값을 0으로 초기화] 굳이 공간을 만들지 않고 조건문과 연산만으로 갯수를 구하자.   
▶한 축에 2개는 고정으로 접해있는 특징을 활용해,  1사분표의 점의 갯수(answer) = cnt(축의 점 갯수 제외) + 2 (축의 점 갯수) 

하기 반복문 조건문을 변경하여 축의 점 갯수를 고정식으로 더해줄 필요는 없다.
  ▷ 반례 )  x= 0 ; x < r2; ++x  //  r2이전의 내원이 x축에 접하는 것까지 계산됨. 이미  x =0에서 y축에 접하는 것을 계산 
  ▷ 정답 ) x = 1 ; x <= r2 ; ++x // 이 범위에서 온전히 하나의 축(x축)에서 접하는 외원과 내원의 갯수 2를 추출.

▶ (▷ 정답 조건문 적용)사분표의 특징을 활용해  answer = 1사분표의 점의 갯수(answer) * 4를 하면된다.

#include<bits/stdc++.h>
using namespace std;
long long solution(int R1, int R2) {
    long long r1 = (long long) R1; // * 연산 시 오버플로우 방지용.
    long long r2 = (long long) R2;
    long long answer = 0;
    //r2 까지 범위에서 x가 r1을 초과할 때 조건문.
    for(long long x = 1; x<= r2; ++x){ // 1사분면의 x축의 내원, 외원의 y 점까지 카운팅. (y축은 아님)
      long long r1_y = 0; 
      long long r2_y = 0;
      r2_y = floor(sqrt((r2 * r2) - (x * x)));  //올림, int형인 r1, r2를 각각 제곱하면 오버플로우 발생. long long으로 casting.
      if(x < r1) r1_y = ceil(sqrt((r1 * r1) - (x * x)));  // 조건문을 통해서 x가 내원 반지름 사이에 존재하는 경우 내원의 y값 내림
      int cnt= r2_y - r1_y + 1;
      answer += cnt;
    }
    return answer *= 4; //사분면이기에 위 1사분면 갯수 * 4
}

---

회고 : 도형에 대한 사고가 부족했다.

입력 값을 제곱 시 오버플로우가 발생할 것을 예상치 못했다. (TC 7 ~ 10 실패)

 

이번 문제는 힌트에 의해 풀게 됐지만, 다음에 동일한 유형이 나오면 손 쉽게 풀자.

---

 

실패 사례

첫번째 풀이

실패 원인 : (r1 ,r2) 가 (1,2) , (2,3) 을 통해 전체의 규칙을 찾으려는 시도를 했던 것 같다. 잘 못된 규칙이다. 

#include <string>
#include <vector>

using namespace std;
/*

(r1, r2)
r1 <= x < r2
for 문 x 번까지 t+= 8 * x;

t+4;

*/
long long solution(int r1, int r2) {
    long long answer = 0;
    for(int x = r1; x<r2;++x){
        answer+=(8*x);
    }
    answer+=4;
    return answer;
}

두번째 풀이

실패원인: 만일 둘다 내람차순 해서 총 외원의 픽셀갯수 - 총 내원의 픽셀 갯수를 하면 외원과 내원이 픽셀 상단 우측 꼭짓점에 각각 접했을 때 점이 두개이나 하나로 계산되는 반례가 생긴다. (그림 x가 3일 때)

(그림 출처 : https://sasca37.tistory.com/320)

#include <string>
#include <vector>
#include<bits/stdc++.h>

using namespace std;
/*
x^2 + y^2 = r^2  ->y^2 = r^2 - x^2  
y^2을 y로 만들고 내림한다. root 5의 경우 -> 2.xxx이니 2로 해야 원 내부에 rectangle 갯수(정수형)를 정확히 셀 수 있다.
바깥 원 rectangle 갯수 - 안 원 rectangle 갯수 + 4
사분표이기에 1사분포의 갯수만 구해서 * 4 하면 답.
*/
long long solution(int r1, int r2) {
    long long answer = 0;
    long long r1_recCnt = 0;
    long long r2_recCnt = 0;
    for(int x= 1; x < r1 ; ++x){
        long long y = floor(sqrt(r1*r1 - x*x));
        r1_recCnt += y;
    }
    for(int x = 1; x < r2; ++x){
        long long y = floor(sqrt(r2*r2 - x*x));
        r2_recCnt += y;
    }
    answer = ((r2_recCnt - r1_recCnt) + 2)  * 4;
    
    return answer;
}

 

---

기본 개념

배열의 stack over flow.

전역변수(전역 배열)는 에 Data영역에 저장.

지역변수(지역 배열), 매개변수는 stack 영역에 저장. 

 

stack과 heap은 한도가 존재.

#include<bits/stdc++.h>
using namespace std;
int arr3[1000001];
int main(void) {
	// 지역변수에서 배열의 사이즈 200,000 ~ 300,000 사이의 특정 값이상이면 stack over flow 발생
	// 전역변수의 경우 1백만까지도 발생하지 않음.
	// 동적 할당시 발생 x (arr1)
	// vector도 동적할당이니 발생 x
	int* arr1 = new int[1000001];
	vector<int> arr2;
	arr2.resize(1000001);
	
	int arr4[300000]; // stack overflow.
	delete arr1;
	
}

https://www.tcpschool.com/c/c_memory_structure

코딩교육 티씨피스쿨