[C++] 백준 2167,1977,2563,10988

2167번 2차원 배열의 합

2차원 배열이 주어졌을 때 (i, j) 위치부터 (x, y) 위치까지에 저장되어 있는 수들의 합을 구하는 프로그램을 작성하시오. 배열의 (i, j) 위치는 i행 j열을 나타낸다.
첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 합을 구할 부분의 개수 K(1 ≤ K ≤ 10,000)가 주어진다. 다음 K개의 줄에는 네 개의 정수로 i, j, x, y가 주어진다(1 ≤ i ≤ x ≤ N, 1 ≤ j ≤ y ≤ M).

#include<iostream>

using namespace  std;

int main() {

	int n, m;
	cin >> n >> m;

	int arr[300][300];

	for (int i = 0; i < n; i++) {

		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
		}
	}

	int testCase, i, j, x, y;
	cin >> testCase;

	
	for (int k = 0; k < testCase; k++) {

		cin >> i >> j >> x >> y;
		int sum = 0;

		for (int r = i - 1; r < x; r++) {
			for (int c = j - 1; c < y; c++) {
				sum += arr[r][c];
			}
		}
		cout << sum<<endl;
		
	}


}

1977번 완전제곱수

M과 N이 주어질 때 M이상 N이하의 자연수 중 완전제곱수인 것을 모두 골라 그 합을 구하고 그 중 최솟값을 찾는 프로그램을 작성하시오. 예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 완전제곱수는 64, 81, 100 이렇게 총 3개가 있으므로 그 합은 245가 되고 이 중 최솟값은 64가 된다.

입력값의 범위가 10000이하의 자연수로 제한되어 있어 10000이하의 완전 제곱수를 모두 구해 벡터에 넣었다. 그후 입력받는 값의 범위 안에 있는 완전제곱수의 합을 구하고 첫번째의 완전 제곱수만 min변수에 저장하여 출력한다.

#include<iostream>
#include <vector>

using namespace  std;

int main() {

	vector<int> perfectNum;

	for (int i = 1;; i++) {

		int square = i * i;
		if (square > 10000) {
			break;
		}
		perfectNum.push_back(square);
	}

	int n,m;
	cin >> m >> n;

	int sum = 0;
	int min;
	bool flag = true;

	for (int sqr : perfectNum) {

		if (sqr >= m && sqr <= n) {
			sum += sqr;
			if (flag)
				min = sqr;
			flag = false;
		}
			
	}

	if (sum == 0)
	{
		cout << -1;
		return 0;
	}

	cout << sum << endl;
	cout << min << endl;

}

2563번 색종이

나에게 많은 빡침을 준 색종이 문제..
처음에 단순하게 입력 색종이의 총면적을 구한뒤 겹치는 부분을 빼면 될 것이라 생각해서 문제를 풀었다. '틀렸습니다'가 떴고 여러 예제를 돌려보니 세번 이상 겹치기 시작하면 틀린다는 것을 알게되었다. 그래서 합집합에 대해 구하는 공식을 찾아보니 아래 그림을 발견하였다.

(출처: https://m.blog.naver.com/galaxyenergy/222007107188)

그래요 세번 겹치는 것까지는 어째저째 만들 것 같은데 그 이상으로 겹치는건 어떻게 해야할지 모르겠더라. 그래도 꾸역꾸역 코드를 보완해서 다시 돌렸는데 이젠 네번이상 겹치는 것에서 문제가 생기는 것인지 9프로에서 틀렸습니다가 뜬다. 뭔가 얄팍한 내 지식으로는 수학적으로 풀지 못했다.

다른 사람의 코드를 찾아보니 도화지 입장의 100*100배열을 만들고 색종이가 해당위치에 있으면 표시를 해서 표시된 도화지 넓이를(배열 원소개수)를 구하더라. 이렇게 단순하게 접근하는 것이 답인 듯 했다.

#include<iostream>
using namespace  std;

int main() {

	bool paper[100][100];
    
	for (int i = 0; i < 100; i++) {
		for (int j = 0; j < 100; j++)
			paper[i][j] == 0;
	}

	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		
		int x, y;
		cin >> x >> y;
        
		//fillPaper(x, y);
		for (int i = x; i < x + 10; i++)
		{
			for (int j = y; j < y + 10; j++)
			{
				paper[i][j] = 1;
			}
		}
	}

	int sum = 0;
	for (int i = 0; i < 100; i++) {
		for (int j = 0; j < 100; j++)
			if (paper[i][j] == 1)
				sum++;
	}

	cout << sum;
}

아래는 삽질한 코드이다. 아마도 색종이가 최대 4개까지 나온다면? 정답일 수도 있다..
Overlap: 겹치는 영역에 대한 정보를 저장할 수 있는 클래스

• leftX: 왼쪽 아래 X좌표
• leftY: 왼쪽 아래 Y좌표
• rightX: 오른쪽 위 X좌표
• rightY: 오른쪽 위 Y좌표

#include<iostream>
#include <vector>
#include<cstdlib>
#include<algorithm>
using namespace  std;

class Overlap {
	
public:	
	int leftX;
	int leftY;
	int rightX;
	int rightY;

public:
	Overlap(int x, int y, int x1, int y1) {
		this->leftX = x;
		this->leftY = y;
		this->rightX = x1;
		this->rightY = y1;
	}
};

int main() {

	vector<Overlap> overlap;
	int n;
	cin >> n;

	vector<pair<int, int>> confetti(n);
	for (int i = 0; i < n; i++) {
		cin >> confetti[i].first >> confetti[i].second;
	}

	int totalArea = n * 100;

	for (int i = 0; i < n-1; i++) {

		overlap.clear();

		for (int j = i + 1; j < n; j++) {

			if (abs(confetti[i].first - confetti[j].first) <= 9
				&& abs(confetti[i].second - confetti[j].second) <= 9)
			{

				int ix= confetti[i].first;
				int iy=confetti[i].second;

				int jx=confetti[j].first;
				int jy=confetti[j].second;

				int leftX = max(ix, jx);
				int leftY = max(iy, jy);

				int rightX = min(ix + 10, jx + 10);
				int rightY = min(iy + 10, jy + 10);

				int lenX = rightX - leftX;
				int lenY = rightY - leftY;
				

				if (overlap.size() == 0) {

					totalArea -= lenX*lenY ;
				}
				else {

					for (int i = 0; i < overlap.size();i++) {

						Overlap area = overlap[i];

						if ((area.leftX <= leftX && leftX <= area.rightX)
							&& (area.leftY <= leftY && leftY <= area.rightY))
						{
							
							int overLenX = min(rightX, area.rightX) - max(leftX, area.leftX);
							int overLenY = min(rightY, area.rightY) - max(leftY, area.leftY);

							//cout << overLenX << endl << overLenY<<endl;
							totalArea -= lenX * lenY - overLenX * overLenY;
						}
					}
				}
				overlap.push_back(Overlap(leftX, leftY, rightX, rightY));

			}
		}
	}
	cout << totalArea;
}

10988번 팰린드롬인지 확인하기

알파벳 소문자로만 이루어진 단어가 주어진다. 이때, 이 단어가 팰린드롬인지 아닌지 확인하는 프로그램을 작성하시오.

팰린드롬이란 앞으로 읽을 때와 거꾸로 읽을 때 똑같은 단어를 말한다.
level, noon은 팰린드롬이고, baekjoon, online, judge는 팰린드롬이 아니다.

말그래도 단어위 위치를 앞뒤로 바꾸었을 때 원래 입력값과 동일하면 팰린드롬 단어라고 판단했다. 단어길이의 반 만큼만 반복문을 돌리고 그 안에서 처음단어와 끝단어를 계속 swap하면 어렵지 않게 구할 수 있다. 이전에 풀었던 팰린드롬숫자도 정수형이 아닌 문자열로 입력받아 같은 방식으로 푼 사람이 있었다.

#include<iostream>
#include<string>

using namespace std;

int main() {

	string word, cpy;
	getline(cin, word); 
	
	cpy = word;		//깊은 복사라 word값 변경되어도 cpy에는 영향 안미침

	int len = word.length();

	for (int i = 0; i <len/2; i++) {

		char temp = word[i];
		word[i] = word[len - 1 - i];
		word[len - 1 - i] = temp;

	}

	if (word == cpy)
		cout << 1;
	else
		cout << 0;
}