[백준/C++] 1065번. 한수

문제

1065번: 한수

---

1. 첫 번째 풀이 (마지막 풀이)

사고 과정

- 1부터 N까지 반복

- 자리수를 분리, 배열 등으로 저장

- 배열의 처음부터 끝까지 반복. [1]에서 [2]를 빼고 d에 저장해둔다. [2]에서 [3]을 뺀 수가 d와 다르다면 break, 끝까지 같다면 count를 1 증가

 

1. 1부터 N까지 반복

2. 자리수를 분리, 배열로 저장

3. 배열의 두 원소를 빼고, 공차를 캐싱

4. 연속해서 빼되, 공차와 다른 순간 종료

5. 끝까지 통과한 수의 개수를 세서 출력

 

코드

#include <iostream>
#include <vector>

int isArithmetic(std::vector<int> nums) {
	for (int j = 2; j < nums.size(); j++) {
		if (nums[j - 2] - nums[j - 1] != nums[j - 1] - nums[j]) {
			return 0;
		}
	}

	return 1;
}

int main() {
	int N, num, count = 0;
	std::cin >> N;
	std::vector<int> nums;

	for (int i = 1; i <= N; i++) {
		num = i;
		nums.clear();

		while (num > 0) {	
			nums.push_back(num % 10);
			num /= 10;
		}
		
		count += isArithmetic(nums);
	}

	std::cout << count;

	return 0;
}

등차수열인지 판별하는 부분을 처음엔 이중 for문으로 구성했는데, count에 더하지 않고 반복문을 두 번 탈출하는 로직을 짜는 게 귀찮았다. 그래서 그냥 별도의 함수로 분리하였다.

 

결과

티어가 뭔지 알게 되어서 켜봤다.

간단하게 성공

---

개선

사고 과정

- 가장 처음 든 생각은, DP로 풀 수도 있지 않을까?

- 예를 들어 N이 110이면 N이 109인 경우 + 110의 한수 여부가 될 것이다. 이를 점화식으로 풀어내면

 

f(n) = { f(n-1) + 1 (n이 한수인 경우)          }

         { f(n-1)       (n이 한수가 아닌 경우)  }

가 된다. 충분히 DP로 풀 수 있어보인다.

 

코드

 

#include <iostream>
#include <vector>

std::vector<int> dp(1001, -1);

// 배열 nums의 원소가 등차수열인지 판별하는 함수
int isArithmetic(std::vector<int> nums) {
	// 길이가 3보다 작다면 1 반환
	if (nums.size() < 3) {
		return 1;
	}

	// 공차 계산
	int d = nums[0] - nums[1];

	// 공차와 다르다면 0 반환
	for (int j = 2; j < nums.size(); j++) {
		if (nums[j - 1] - nums[j] != d) {
			return 0;
		}
	}

	// 공차가 모두 같다면 1 반환
	return 1;
}

// 한수인지 판별하는 함수
int isHansu(int i) {
	int num = i;
	std::vector<int> nums;

	// 자리수 분할
	while (num > 0) {
		nums.push_back(num % 10);
		num /= 10;
	}

	// 등차수열 판별 후 반환
	return isArithmetic(nums);
}

// dp 배열의 값을 받아오는 함수, 정보가 없다면 재귀적 호출로 계산
int getDP(int i) {
	// 잘못된 값이 들어오면
	if (i < 0) {
		// 에러 반환
		return -1;
	}

	// 정보가 있다면 반환
	if (dp[i] != -1) {
		return dp[i];
	}

	// 정보가 없다면 계산 후 반환
	dp[i] = getDP(i - 1) + isHansu(i);

	return dp[i];
}

int main() {
	int N = 0;
	std::cin >> N;

	dp[0] = 0;
	dp[1] = 1;

	std::cout << getDP(N);

	return 0;
}

내용 파악을 쉽게 하기 위해 한수 구하는 부분을 함수로 분리했다.

 

결과

결과는 성공적. 메모리 사용량과 시간도 변함없다.

다만 기존 방식은 숫자가 입력될 때마다 새로 계산하는 방식이며, DP를 활용한 방식은 이전에 구하지 않은 부분만 새로 계산한다. 비록 이번 문제는 입력이 하나 뿐이지만, 입력이 많아질수록 성능은 비교적 더 빨라질 것이다.

---

가장 효율적인 코드

https://www.acmicpc.net/source/29664330

jinhan814님의 C언어 코드. 원래 C++로 필터링해서 가져오지만, 이번 문제는 참신해서 이걸로 가져와봤다.

jinhan814님은 N이 1,000보다 작다는 점을 이용해, 1,000 이하의 모든 한수를 배열에 하나씩 저장한 후 출력하셨다. N이 10,000만 돼도 배열을 만드는 건 어려워지겠지만, 오히려 배열 크기만 버텨준다면 배열을 생성하는 로직을 짜서 사용할 수도 있어보인다. 그래서 매우 빠른 속도로 해당 문제를 푸셨다.

https://www.acmicpc.net/source/16433931

C++에선 gpfl0712님이, 비교적 정석(?)적으로 올린 풀이가 있었다.

코드의 작동은 내가 쓴 코드와 비슷하지만, 한수 판별법이 신기했다.

100 미만의 수는 반드시 한수다. 문제는 100 이상인데, (i / 100 + i % 10) == (i / 10 % 10 * 2)라는 식을 사용하셨다.

이는 백의 자리 + 일의 자리 == 십의 자리 * 2, 등차수열의 성질이다. N이 최대 999라는 점을 이용해 단 한 줄로 한수 판별법을 알아내셨다.

 

내 코드와 비교

나는 문제를 거의 있는 그대로 풀었다. 사실상 구현에 지나지 않았다. 그러나 위 두 분은 문제의 조건을 100% 활용하여 더 짧고 간결한 코드를 작성하셨다.

나는 "이해하기 쉽고 확장성이 높은" 코드를 지향하기 때문에 문제의 제한 조건에 큰 신경을 쓰지 않는다. 그래서 나는 코드를 짤 때 항상 '100 만을 넣어도 작동하는가?'를 되뇌고는 한다. 코딩 스타일의 차이로도 볼 수 있지만, 알고리즘 문제는 빠른 시간 내에 답을 구해야하는 경우가 많으니, 위 풀이들처럼 사고하는 방식을 익혀야할지도 모르겠다.

---

강평

바로 다음 문제인 A한수에 비하면 훨씬 쉬웠던 문제. Brute-force하게 한 번, DP로 한 번 풀어보며 스킬을 점검할 수 있었다. 다만 다른 풀이들보다 코드 길이가 길어져서 다른 사람이 보기에도 구조 파악이 쉬울지는 잘 모르겠다.