Lv 2. 두 원사이의 정수 쌍

2025. 1. 11. 18:28·Algorithm & Data Structures/Programers

 

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

 

프로그래머스

SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프

programmers.co.kr

 

 

 

두 개의 원 사이에 존재하는 격자점의 개수를 계산하는 문제다.

 위의 이미지를 보면 두 개의 원이 그려져 있다. 

작은 원은 반지름 r1​ , 큰 원은 반지름 r2 를 가지고 있다. 

이 두 원 사이에 포함된 정수 좌표를 찾는 것이 문제의 핵심이다. 

그림을 보면 두 원 사이에 위치한 파란색 점들이 우리가 찾으려는 정수 좌표들이다. 


코드는 각 x 좌표에서 y 값의 범위를 계산해 파란색 점들의 개수를 세는 방식으로 동작한다.

원의 방정식인 x제곱 + y제곱 = r제곱 를 사용하여

특정 x 좌표에서 가능한 y 값의 범위를 구할 수 있다.

예를 들어, x 값이 고정되었을 때,

작은 원 r1 의 방정식에 의해 계산된 y 값은 y의 하한선이 되고,

큰 원 r2 의 방정식에 의해 계산된 y 값은 y의 상한선이 된다.

 

이때 y 값은 반드시 정수여야 하므로,

하한선에는 올림을, 상한선에는 내림을 적용한다.

이 과정을 반복문을 통해 x 좌표가 1부터 r2​ 까지 순회하면서 수행한다.

각 x 좌표마다 계산된 y 값의 범위에서 가능한 정수 좌표의 개수는 end-start+1 로 구할 수 있다.

이 값을 누적하여 제1사분면에서 파란색 점들의 개수를 구한다.

최종적으로 이 값에 4를 곱해 전체 원(4개의 사분면)에 걸친 모든 격자점을 계산한다.

코드에서 Math.sqrt는 원의 방정식을 기반으로 y 값을 계산하기 위해 사용된다. 

Math.ceil과 Math.floor는 정수 범위를 한정하기 위한 중요한 역할을 한다. 

 

 

 

class Solution {
    public long solution(int r1, int r2) {
        long answer = 0;

        for (int i = 1; i <= r2; i++) {
            int start = (int) Math.ceil(Math.sqrt((long) r1 * r1 - (long) i * i));
            int end = (int) Math.floor(Math.sqrt((long) r2 * r2 - (long) i * i));

            answer += end - start + 1;
        }

        return answer * 4;
    }
}

'Algorithm & Data Structures > Programers' 카테고리의 다른 글

Lv 2. 충돌위험 찾기  (0) 2025.01.16
Lv 2. 석유 시추  (0) 2025.01.14
Lv 2. 혼자서 하는 틱택토  (0) 2025.01.09
Lv 3. 표 편집  (0) 2025.01.07
Lv 2. N-Queen  (1) 2025.01.03
'Algorithm & Data Structures/Programers' 카테고리의 다른 글
  • Lv 2. 충돌위험 찾기
  • Lv 2. 석유 시추
  • Lv 2. 혼자서 하는 틱택토
  • Lv 3. 표 편집
Geisha
Geisha
개발 일기
  • Geisha
    Geisha
    Geisha
  • 전체
    오늘
    어제
    • 분류 전체보기 (343) N
      • Algorithm & Data Structures (261) N
        • BOJ (119) N
        • SWEA (1)
        • Programers (137)
        • Data Structures (3)
      • DB (29)
        • SQL (23)
        • RDBMS (2)
      • Java (1)
        • Class (1)
      • Spring (5)
        • Spring MVC (1)
        • Annotations (1)
      • CS (36)
        • 운영체제 (13)
        • 네트워크 (5)
      • Tool (6)
        • Git (5)
        • AWS (1)
      • Project (1)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    다이나믹 프로그래밍
    유니온파인드
    백준
    dfs
    후위순회
    DynamicProgramming
    골드
    SQL
    Stack
    구현
    투포인터
    baekjoon
    프로그래머스
    programmers
    다익스트라
    자바
    알고리즘
    Dijkstra
    Union-Find
    PriorityQueue
    algorithm
    동적계획법
    Java
    이분탐색
    dp
    BFS
    스택
    경로압축
    백트래킹
    binarySearch
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.0
Geisha
Lv 2. 두 원사이의 정수 쌍
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.