2022.06.29

50,51. 영지(territory) 선택 : (small),(large)

문제 설명: 그림과 같은 이차원 배열과 영역의 크기(wide,hight)가 주어졌을 때, 영역안의 숫자의 합이 최대가 되는 값을 구하는 것

이 문제는 50번은 입력값의 크기가 작은 경우, 51번은 큰 경우로 51번에서는 시간제한이 주어졌다.
50번은 정말 쉽게 풀었다. 정직한 방법으로 for문을 총4번 돌리는 방식으로 풀었다.
당연하겠지만 51번에 같은 코드를 적용했을 때는 시간제한에 모두 걸렸다..

꽤 오래 잡고 고민했는데, 결론이 안나와서 강의 초반부를 참고했다.
dynamic programing의 일종으로 볼 수있는 방법인듯 한데, 숫자를 입력할 때 그 위치까지의 합을 입력하는 것을 통해, 구간의 합을 계산할 때 반복문을 돌리지 않고, 특정 위치의 값들을 빼고 더함으로써 영역내의 숫자합을 구할 수 있다.

int main(){
	//freopen("input.txt","rt",stdin);
	
	int wide,length,tmp;
	cin>>length>>wide;
	vector<vector<int>> orange(length,vector<int>(wide,0));
	for(int i=0; i<length; i++){
		for(int j=0; j<wide; j++){
			cin>>tmp;
			
			if(i==0&&j==0){
				orange[i][j]=tmp;
			}
			else if(i==0){
				orange[i][j]=orange[i][j-1]+tmp;
			}
			else if(j==0){
				orange[i][j]=orange[i-1][j]+tmp;
			}
			else{
				orange[i][j]= orange[i-1][j]+orange[i][j-1]-orange[i-1][j-1]+tmp;
			}
		}
	}
	
	int w,l,sum,answer=0;
	cin>>l>>w;
	for(int i=l-1; i<length; i++){
		for(int j=w-1; j<wide; j++){
			if(i<l&&j<w){
				sum = orange[i][j];
			}
			else if(i<l){
				sum = orange[i][j]-orange[i][j-w];
			}
			else if(j<w){
				sum = orange[i][j]-orange[i-l][j];
			}
			else{
				sum = orange[i][j]-orange[i-l][j]-orange[i][j-w]+orange[i-l][j-w];
			}
			
			if(sum>answer){
				answer = sum;
			}
			
		}
	}
	cout<<answer;
	return 0;
}

나는 배열을 다루는 과정에서 테두리 부분밖으로 벗어나는 걸 조절하려고 if문을 많이 사용했는데, 애초에 배열을 크게 잡고 테두리는 0으로 초기화시켜뒀으면 됐을 문제였다.

결론

이차원배열을 다룰 때 미리 초기화해놓고 테두리값을 설정하면 더 명확하게 값을 다룰 수 있다.
초기값들의 합을 조작함으로써 더 간단하게 구간내의 합을 구할 수 있다.

52. uglyNumbers

문제 설명: 2,3,5만을 소수로 가지는 수를 uglyNumbers라 한다. 자연수 n이 주어졌을 때 n번째 uglyNumber를 구하는 것.

int minNum(int a,int b, int c){
	return min(a,min(b,c));
}

int main(){
	//freopen("input.txt","rt",stdin);	
	int n, cnt=1;
	cin>>n;
	
	vector<int> uglyNums(2,0);
	
	int p2=1,p3=1,p5=1;
	int num1, num2, num3, tmp;
	uglyNums[1]=1;	
	
	while(true){		
		num1=uglyNums[p2]*2;		
		num2=uglyNums[p3]*3;
		num3=uglyNums[p5]*5;
		
		tmp = minNum(num1,num2,num3);
		uglyNums.push_back(tmp);
		if(tmp==num1){
			p2++;
		}
		if(tmp==num2){
			p3++;
		}
		if(tmp==num3){
			p5++;
		}
		
		if(uglyNums.size()==n+1){
			cout<<uglyNums[n];
			break;
		}
	}	
	return 0;
}

해결 방법은 uglyNumber는 결국 uglyNumber에 2,3,5 중 하나를 곱한 값으로 이루어진다는 특성을 이용하는 것이다.

처음에 내가 푼 방식은 소수인 것, 소수가 아닌 것중에서 2,3,5를 제외한 다른 수로 나누어지는 것은 uglyNumber가 아니라고 판단해 조건문을 계속 돌리는 방식이었는데, 하나하나 소수인지 판단하고 다른수로 나누어지는지 확인하니 당연히 time limit에 걸렸다.
정말 오래 고민해봐도 잘 느낌이 안와서 강의 초반부에 힌트를 참고해서 풀었다.

결론

- 좀 더 거시적인 관점에서 배열을 다룰 수 있도록 한다. 값 하나하나를 확인하면서 가는 것만이 방법이 아니다.
- 투포인터는 여러 조건이 있을 때 포인터마다 각각의 조건에 맞게 움직이도록 하여 문제를 해결할 수 있다. 이 문제도 투포인터 문제의 종류중 하나였다.