[백준/c++] 14650 - 걷다보니 신천역 삼 (Small)

www.acmicpc.net/problem/14650

14650번: 걷다보니 신천역 삼 (Small)

---

1) 풀이

뭔가 풀이 방법은 알겠는데, 효율적이지 못해서 시간초과가 많이 나온 문제😥

정말... 나빼고 전부 3의 배수가 자리수 다 합해도 3의 배수라는 걸 다 알고 있었던 걸까....충격적이야

누군가는 내가 더 충격적이겠지만 흑흑 이게 문과생의 한계인걸까

하지만 난 의지의 문과생,,, 해냈다구요..~

 

1. 0, 1, 2로 만들 수 있는 한자리수는 3의 배수가 없다.

»n에 1이 입력되면 바로 0을 출력하고 프로그램 종료

2. n자리수는 0으로 시작할 수 없다.

»맨 앞에 오는 수는 1과 2로 제한

3. 3의 배수는 각 자리를 모두 더해도 3의 배수이다.

»벡터에 만들 수 있는 자연수를 push하고 n개가 차면, 그 수들을 차례대로 더해서 3의 배수인지를 확인하고, 3의 배수를 카운팅하는 변수를 조정한다. 

4. n자리수의 각 자리는 0,1,2의 경우를 모두 고려해주어야 한다.(단, 맨 처음자리는 1,2만 고려한다)   

»재귀를 통해 각 자리를 바꿔주고, 각각의 경우가 3의 배수인지 체크한다.

 

이외에도, 함수의 매개변수로 넘겨주는 벡터는 참조형으로 넘겨주어야 하는데 이에 대한 설명은 아래의 참고자료를 참고하면 좋을듯 하다.

 

2) 최종 소스코드

#include <bits/stdc++.h>
using namespace std;
int n;
int cnt = 0;
void bruteForce(vector<int>&v,int cur) { 
	v.push_back(cur);//하나씩 뒤에 넣어줌.
	if (v.size() == n) { //벡터 안에 든 숫자가 n자리가 되면 그 n자리의 숫자들을 다 더함
		int sum = 0;
		for (int i = 0; i < n; i++) {
			sum += v[i];
		}
		if (sum % 3 == 0) cnt++; //다 더한 값이 3의 배수이면 카운팅

		return;
	}
	else {//n자리를 아직 못채웠다면
		for (int i = 0; i < 3; i++) {
			bruteForce(v,i); //0부터 재귀
			v.pop_back(); //재귀가 끝나면, 끝에 들어온 수를 pop하고 다음 수 넣기
		}
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	
	cin >> n;

	if (n == 1) { //0,1,2로 만드는 한자리수는 3의 배수가 없다
		cout << 0 << '\n';
		return 0;
	}
	else {
		for (int i = 1; i <= 2; i++) {//제일 앞자리에는 1,2밖에 오지 못함
			vector<int>v; //n자리수 저장
			bruteForce(v,i); //맨앞 자리수와 벡터를 매개변수로 보냄 
		}
	}
	cout << cnt << '\n';
}

3) 참고자료

modoocode.com/141