[백준] 1065 한수 c++

2021. 6. 26. 00:38·알고리즘 이론/백준
목차
  1. 1065. 한수

1065. 한수

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

 

1065번: 한수

어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나

www.acmicpc.net

 제출 수가 굉장히 높은 것으로 보아 이 문제 역시 중요한 기초문제인것 같다. 하지만 필자는 문제의 풀이를 생각해내는데 꽤 많이 고민했다. 문제에서 주어진 '한수'를 어떻게 저장하면 좋을지 고민해가며 100~999까지의 '한수'를 모두 종이에 적어보았지만 어떠한 규칙도 발견하지 못했고, 규칙이 있어도 굉장히 복잡해질 것 같았다. 때문에 입력이 주어지면 입력된 정수까지의 한수를 모두 찾아서 세어주는 방식으로 문제를 해결해 보았다.


 

이 문제의 입력 조건을 살펴보면 1,000보다 작거나 같은 자연수 N이다. 입력이 굉장히 작으므로 모든 경우의 수를 시도해보아도 제한시간 내에 충분히 풀 수 있다.

 

 

먼저 '한수'가 대체 무엇인지 정확하게 알 필요가 있다. 어떤 양의 정수의 각 자리가 등차수열을 이룬다면 그 수는 한수이다. 즉, 1~99까지의 수는 모두 한수이다. 때문에 100미만의 자연수가 입력으로 주어질 경우, 아무런 계산없이 해당 수를 출력해주면 된다. 왜냐하면 100미만의 수는 한수이기 떄문이다.

if (num < 100) cout << num;

그렇다면 100이상의 수는 어떻게 처리해야할까?

100이상의 자연수가 입력으로 들어오면 100부터 입력된 자연수까지의 수가 한수인지 판단해준다.

for()문을 통하여 100부터 입력받은 수까지 cnt()라는 함수를 호출하여 처리하였다.

 

cnt()함수에서는 전달받은 값을 10으로 나눈 나머지를 벡터에 저장해주었다. 그리고 그 수를 10으로 나누어주고 다시 10으로 나눈 나머지를 벡터로 저장했다.

while (num > 0) {
		v.push_back(num % 10);
		num /= 10;
	}

이 과정을 거치는 이유는 정수를 통채로 살펴보는 것이 아닌, 정수의 각 자리수의 숫자를 살펴보기 위함이다.

위 과정을 거치면, v의 첫번째 원소는 전달된 숫자의 일의 자리를 저장하고 v의 두번째 원소는 십의 자리 마지막으로 v의 세번째 원소는 백의 자리 숫자가 된다. 이를 통하여 우리는 각 자리수의 숫자를 알 수 있게되었다.

 

--> 각 자리수를 구하는 것을 응용하는 문제가 은근 많다! 기억해 놓기로하자!!

 

 

다시 '한수'에 집중해보자. 필자가 힘들게(사실은 컴퓨터가ㅎ.,ㅎ) 벡터에 저장한 각 자리의 수들이 등차수열을 이루는지 확인한다. 

어떻게??!!

if (v[2] - v[1] == v[1] - v[0]) {		
		return 1;
	}

그냥 우리 모두가 잘 아는 if문을 사용해준다. 여기서 return 값이 1인 이유는 무엇일까?

필자는 int cnt(int num){}형식의 함수를 생성하였기 때문에 반환값으로 int값을 넘겨주어야한다.

때문에 만일 num이 등차수열을 만족한다면 1을 반환하고 만족하지 못하면 0을 반환하였다. 그리고 main함수에서 반환된 값을 sum이라는 변수에 더해줌으로써 모든 한수를 셀 수 있게된다.

 

더보기

코드:

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> v;
int cnt(int num) {
	v.clear();
	while (num > 0) {
		v.push_back(num % 10);
		num /= 10;
	}

	if (v[2] - v[1] == v[1] - v[0]) {
		
		return 1;

	}
	else return 0;

}

int main() {
	ios::sync_with_stdio(0);
	cout.tie(); cin.tie();
	int sum = 99;
	int num;
	cin >> num;
	if (num < 100) cout << num;
	else if (num == 1000) cout << 144;
	else {
		for (int i = 100; i <= num; i++) {
			sum+=cnt(i);
		}
		cout << sum;
	}
}

 

저작자표시 비영리 (새창열림)

'알고리즘 이론 > 백준' 카테고리의 다른 글

[5032] 탄산 음료 C++  (0) 2021.06.26
[백준] 2863 이게 분수?  (0) 2021.06.26
[백준] 1427 소트인사이드 c++  (0) 2021.06.26
[백준] 1026번 보물 c++  (1) 2021.06.26
[백준] 2798 블랙잭  (0) 2021.06.21
  1. 1065. 한수
'알고리즘 이론/백준' 카테고리의 다른 글
  • [백준] 2863 이게 분수?
  • [백준] 1427 소트인사이드 c++
  • [백준] 1026번 보물 c++
  • [백준] 2798 블랙잭
senyalog
senyalog
개발 블로그 https://github.com/iamyunjuda
  • senyalog
    Senya의 개발 블로그
    senyalog
  • 전체
    오늘
    어제
    • 분류 전체보기 (77)
      • 일상 (6)
      • 알고리즘 이론 (14)
        • 백준 (8)
      • 개발 (47)
        • Server (7)
        • 인턴 (11)
        • Javascript (0)
      • 경제 (4)
  • 블로그 메뉴

    • Github
    • 홈
  • 링크

    • Github
  • 공지사항

  • 인기 글

  • 태그

    인턴
    알고리즘
    대학생
    개발공부
    컴공
    이마고웍스
    인턴생활
    TypeScript
    일상
    코딩
    GIT
    생각
    개발자
    깃
    백준문제
    개발
    nestjs
    카페
    백준
    경제
    공대생
    알고리즘공부
    백엔드
    공부
    서버
    C++
    MSA
    대학생인턴
    코딩테스트
    백준풀이
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
senyalog
[백준] 1065 한수 c++
상단으로

티스토리툴바

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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