백준 2275번 C/C++

www.acmicpc.net/problem/2775

2775번: 부녀회장이 될테야

이번 문제를 보고 처음 생각한 풀이법은 재귀함수였습니다.

그렇게 재귀함수를 적으며 든 생각은 굳이 재귀함수로 사용하지 않고 풀어도 풀리겠는걸..? 이라는 생각이 들어서

재귀함수를 지우고 그냥  main함수 안에서 모든 것을 해결했습니다. 

 

반복문을 많이 쓰지 않고 풀고 싶었으나 1차적으로 문제에 대한 답이 나오는 방향을 선택을 하였고 teseCase가 그렇게 많지 않아서 그런지 시간 초과는 나오지 않았습니다. 

 

제 코드는 다음과 같습니다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>

//a층의 b호에 살라면 자신의 아래층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을
//데려와서 살아야한다.
//아파트는 0층부터 존재한다. 그리고 각 층은 1호부터 존재한다.
//0층 i호에는 i명이 산다.

int testCase[1000000];	//값을 저장할 배열
int level[15];			//각 호에 있는 사람 수를 구할 배열

int main()
{	
	int T;
	scanf("%d", &T);	//T의 수를 받아옴.

	for (int i = 1; i <= 14; i++) {	//level 배열 초기화
		level[i] = i;
	}

	int k, n;	int result = 0;
	for (int i = 0; i < T; i++) {
		scanf("%d", &k);	//층 수를 받아옴
		scanf("%d", &n);	//호 수를 받아옴

		while (k != 0) {
			int changer = 0;
			for (int j = 1; j <= n;j++) {
				changer += level[j];
				level[j] = changer;

				result = level[j];
			}
			k--;
						
		}
		testCase[i] = result;

		for (int i = 1; i <= 14; i++) {	//level 배열 초기화
			level[i] = i;
		}
	}

	for (int i = 0; i < T; i++) {
		printf("%d\n", testCase[i]);
	}
}

이 문제를 풀면서 착각을 하였던 점은 수식은 맞는데 처음에 문제 예시와 같이 2 1 3 2 3을 입력하면 6, 15가 나온다는 점이었습니다.

왜 이렇게 나오지 생각을 하던 때 저번과 같은 실수를 저지르고 있다는 사실을 깨닫게 되었습니다.

여러분도 아시겠지만 배열이 다시 처음으로 돌아온다는 생각을 하고 있었던 것입니다. 저는 배열 안의 수를 바꾸고 있었지만 저는 그 과정을 무시하고 진행을 해서 다음 단계에서는 층이 이미 높아진 상태로 시작을 하는 것이었습니다.

 

손으로 문제를 풀때도 저는 생각을 배열이 다시 초기화된다고 생각을 하여서 무슨 문제이지 생각을 하다 문뜩 저번에 했던 실수가 떠올라서 다시 level 배열 초기화를 하니 해당 문제에 대한 답이 나왔습니다.

 

역시 이러한 문제를 풀거나 코딩을 할 때에는 직접 아파보고 그 아픔에 대해 생각을 해보는 것이 중요한 것 같습니다.