[백준/C++] 2407 조합 (S3)

유형	난이도	완료일	링크	특이사항
DP	실버3	23/03/30	https://www.acmicpc.net/problem/2407

 

 

틀린 코드

#include <iostream>
#include <string>

using namespace std;

string arr[101][101];

int main(void)
{
	
	int n, m;
	cin >> n >> m;
	
	
	for(int i=1;i<=100;i++)
	{
		arr[i][0] = "1";
		arr[i][1] = to_string(i);
		arr[i][i] = "1";
		
	}	
	
	for(int i=1; i<=100; i++)
	{
		for(int j=1; j<=i-1; j++)
		{

			int n1,n2,idx=0, p=0, s1,s2;

			s1 = arr[i-1][j].length();
			s2 = arr[i-1][j-1].length();
			
			
			while(s1 || s2 || p)
			{
				if(s1)
					n1 = arr[i-1][j][(s1--) - 1]-'0';
				if(s2)
					n2 = arr[i-1][j-1][(s2--) - 1]-'0';
				
				arr[i][j].append(to_string((n1+ n2+ p) %10));
				
				if(n1+n2+p > 9)
					p = 1;
				else
					p = 0;
				
				n1 = 0; n2 = 0;
			}

		}
	}
	
	cout << arr[n][m];
	
}

C++에서 숫자형으로 다룰 수 없는 큰 수를 출력해야 하기 때문에 숫자를 문자열로 바꾸어 덧셈 해야 한다. 위 코드는 이항계수의 성질을 이용해서 1C1부터 100C100까지 미리 계산하는데, append 함수로 맨 뒤에 값을 추가하니 n1+n2+p의 결과가 두 자리 수일 때 ‘0’이 먼저 추가되어 계산 결과가 10이라면 ‘01’과 같은 형태로 저장되는 오류가 있었다.

정답 코드

#include <iostream>
#include <string>

using namespace std;

string arr[101][101];

int main(void)
{
	
	int n, m;
	cin >> n >> m;
	
	
	for(int i=1;i<=100;i++)
	{
		arr[i][0] = "1";
		arr[i][1] = to_string(i);
		arr[i][i] = "1";
		
	}	
	
	for(int i=1; i<=100; i++)
	{
		for(int j=2; j<=i-1; j++)
		{
			int n1=0, n2=0, idx=0, p=0, s1=0, s2=0;

			s1 = arr[i-1][j].length();
			s2 = arr[i-1][j-1].length();
			
						
			while(s1 || s2 || p)
			{
				if(s1)
					n1 = arr[i-1][j][(s1--) - 1]-'0';
				if(s2)
					n2 = arr[i-1][j-1][(s2--) - 1]-'0';
				
				int k = (n1+n2+p) %10;

				arr[i][j].insert(0, to_string(k));

				if(n1+n2+p > 9)
					p = 1;
				else
					p = 0;
				
				n1 = 0; n2 = 0;
			}
			
		}
	}
	
	cout << arr[n][m];
	
}

append 대신 insert를 이용해서 0, 즉 맨 앞에 문자를 추가했다.

arr[i][1] = to_string(i); 부분을 arr[i][1] = i+’0’으로 바꿨다가 계속 잘못된 답을 출력해서 고민했었다.

i가 두 자릿수 이상이 되면 i+’0’으로 의도한 문자열로 바꿀 수 없다. 원래대로 to_string으로 바꿔서 맞았다.

역시 아직 문자열을 다루는게 많이 서툰 것 같다. 문자열 관련 문제를 많이 연습해야겠다.