[백준 C++] 2292번, 2775번

2292번 - 벌집

2292번 문제

 

 

<코드 작성>

변수 cnt는 방의 번호, 변수 end는 cnt번방에 들어갈 수 있는 최대 숫자가 대입된다.

변수 num은 end의 범위를 증가시키기 위함이다. 

end를 1로 초기화(N==1 경우 무조건 1번 방이기 때문)하고, for문을 통해 end에 (6 * i)를 더해준다.  

입력받은 N이 end를 넘지 않을 경우 cnt = 1 + i를 통해 방 번호를 저장하고 반복문을 종료한다. 

입력받은 N이 end보다 클 경우 num += 2를 통해 end의 범위를 증가시킨다. 

 

1번 방 : 1 (end1 = 1 + 6 * 0 = 1)

2번 방 : 2 ~ 7 (end2 = end1 + 6 * 1 = 7)

3번 방 : 8 ~ 19 (end3 = end2 + 6 * 2 = 19)

4번 방 : 20 ~ 37 (end4 = end3 + 6 * 3 = 37)

5번 방 : 38 ~ 61 (end5 = end4 + 6 * 4 = 61)

6번 방 : 61 ~...

 

#include <iostream>
using namespace std;

int main() {
	int N;
	cin >> N;

	int cnt = 1, num = 0, end = 0;
    
	if (N == 1) cout << cnt; //N이 1일경우 1번방
	else { //N > 1일 경우 
		num = 1; end = 1; //num: end의 범위를 결정할 때 사용, end: 방 번호를 결정할 때 사용
		for (int i = 1; i <= num; i++) {
			end += (6 * i);
			if (N <= end) {
				cnt = 1 + i;
				break;
			}
			else num += 2;
		}

		cout << cnt;
	}
	return 0;
}

 

 

입력받은 N이 end를 기준으로 방 번호가 나뉘고 end의 범위가 증가하는 규칙을 찾으면 해결할 수 있는 문제라고 생각합니다. 

조금 더 생각해보면 변수 하나 정도는 덜 사용하고 문제를 풀 수 있을 것 같지만 당장은 생각이 나지 않아 이후에 해결할 경우 수정하여 코드를 추가하겠습니다. 

 

 

2775번 - 부녀회장이 될 테야

2775번 문제

 

<코드 작성>

ex) k = 2, n = 3
     -> (k = 1 n = 1) + (k = 1 n = 2) + (k = 1 n = 3)  
     -> (k = 0 n = 1) + (k = 0 n = 2 + k = 0 n = 1) + (k = 0 n = 3 + k = 0 n = 2 + k = 0 n = 1) 
     -> (k=0 n=1) * 3  +  (k=0 n=2) * 2  +  (k=0 n=3) * 1 = 3 + 4 + 3 = 10
     => 결론 : 재귀함수 사용!

몇층(k)을 입력받던 무조건 0층으로 돌아가 사람 수를 카운트 해야하기에 재귀함수를 사용(getNum).

n이 1일 경우 1을 반환하고, k가 0일 경우 n을 반환한다.

그리고 앞의 두 경우가 아닐 경우는 재귀함수를 호출(getNum(k -1, n) + getNum(k, n - 1))한다. 

 

 

#include <iostream>
using namespace std;

	//1층 3호 -> 0층 1호: 1명, 0층 2호: 2명, 0층 3호: 3명 => 총 6명
	//2층 3호 -> 1층 1호 : 1명, 1층 2호: 3(1+2)명, 1층 3호: 6(1+2+3)명 => 총 10명
	//3층 3호 -> 2층 1호 : 1명, 2층 2호: 4(1+(1+2))명, 2층 3호: 10(1+(1+2)+(1+2+3))명 => 총 15명
    
int getNum(int k, int n) {  //재귀함수
	if (n == 1) return 1;
	if (k == 0) return n;
	return getNum(k - 1, n) + getNum(k, n - 1);
}

int main() {
	int T;
	cin >> T;

	int k, n;
	for (int i = 0; i < T; i++) {
		cin >> k >> n;
		cout << getNum(k, n) << '\n';
	}
	return 0;
}

getNum함수의 return 값을 구할 때, 정확한 규칙성을 찾기 어려워 getNum(k - 1, n)만 return 값으로 두고 고민을 했습니다. 

 

 

감사합니다!

2022.02.19