[백준] 2230번: 수 고르기 C++로 풀어보기

2023. 8. 16. 23:51·Algorithm/Baekjoon(C++)

https://www.acmicpc.net/problem/2230

 

2230번: 수 고르기

N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어

www.acmicpc.net

2230번 설명

생각

투 포인터를 사용하여 문제를 해결 할 수 있다.

 

(투 포인터에 대해서 궁금하다면 밑의 링크를 클릭해서 바킹독님의 강의를 보면 된다. 이 문제에 대한 풀이도 해주신다!)

https://www.youtube.com/watch?v=I_0aAKzu0m8&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=21

 

포인터 두 개 st, en을 둔다.

 

1. en을 옮긴다.
2. en - st >= m 이상일 때를 찾는다.
3. en-st가 min보다 작다면min을 갱신한다.
4. st를 옮긴다.
5. 2번 조건에 만족하면 min을 갱신한다.(불만족할때까지)
6. 불만족하면 en을 옮긴다.

 

위 과정을 반복하면 된다.

 

코드
#include <bits/stdc++.h>
using namespace std;

int arr[100005];
int least = 0x7fffffff; // 차이의 최솟값을 저장할 변수

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	
	int n, m;
	cin >> n >> m;

	for (int i = 0; i < n; i++) { // 입력
		cin >> arr[i];
	}

	sort(arr, arr+n); // 오름차순 정렬

	int en = 0; // en을 0으로 둔다
	
	for (int st = 0; st < n; st++) { 

		while (en < n && arr[en] - arr[st] < m) { // en이 n보다 작고 두 수의 차이가 m보다 작으면
			en++; // 포인터 en을 증가시킨다
		}
	
		if (en == n) { // en이 n이라면 (범위를 넘어갔으므로)
			break; // while문을 종료한다
		}

		int bet = arr[en] - arr[st];


		if (bet < least) { // bet이 least보다 작다면
			least = bet; // least에 bet을 저장한다
		}
		
	}

	cout << least; // least를 출력한다

}

 

결과

2230번 결과

 

큰 수를 나타낼 때는 0x7fffffff를 나타내면 좋다는 사실을 배웠다(0x7fffffff는 표현할 수 있는 가장 큰 32비트 값이다.).

저작자표시 비영리 변경금지 (새창열림)

'Algorithm > Baekjoon(C++)' 카테고리의 다른 글

[백준] 1644번: 소수의 연속합 C++로 풀어보기  (0) 2023.08.17
[백준] 1806번: 부분합 C++로 풀어보기  (0) 2023.08.17
[백준] 2805번: 나무 자르기 C++로 풀어보기  (1) 2023.08.12
[백준] 1019번: 책 페이지 C++로 풀어보기  (0) 2023.08.12
[백준] 1931번: 회의실 배정 C++로 풀어보기  (0) 2023.08.09
'Algorithm/Baekjoon(C++)' 카테고리의 다른 글
  • [백준] 1644번: 소수의 연속합 C++로 풀어보기
  • [백준] 1806번: 부분합 C++로 풀어보기
  • [백준] 2805번: 나무 자르기 C++로 풀어보기
  • [백준] 1019번: 책 페이지 C++로 풀어보기
퀵차분
퀵차분
웹 프론트엔드 개발자를 꿈꾸고 있습니다 :)
  • 퀵차분
    QC's Devlog
    퀵차분
  • 전체
    오늘
    어제
    • 분류 전체보기 (165)
      • Frontend (28)
        • HTML, CSS (7)
        • Javascript (3)
        • React (11)
        • Typescript (2)
        • Next.js (4)
      • Node.js (3)
      • Study (40)
        • Modern JS Deep Dive (13)
        • SQL (1)
        • Network (1)
        • 프롬프트 엔지니어링 (4)
        • 인공지능 (9)
        • 시스템프로그래밍 (11)
        • 선형대수학 (1)
      • Intern (4)
      • KUIT (20)
      • Algorithm (48)
        • Baekjoon(C++) (26)
        • Programmers(JavaScript) (22)
      • 우아한테크코스(프리코스) (4)
      • Project (7)
        • PROlog (4)
        • Nomadcoder (2)
      • 생각 (4)
      • Event (7)
  • 블로그 메뉴

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

  • 공지사항

  • 인기 글

  • 태그

    next.js
    HTML
    프롬프트 엔지니어링
    리액트
    음악추천
    typescript
    시스템프로그래밍
    인공지능
    오블완
    알고리즘
    프로그래머스
    타입스크립트
    프로그래머스 자바스크립트
    티스토리챌린지
    자바스크립트
    javascript
    KUIT
    react
    프론트엔드
    백준
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
퀵차분
[백준] 2230번: 수 고르기 C++로 풀어보기
상단으로

티스토리툴바