말랑한 하루

[BAEKJOON] 1032, 1037, 1145, 1052, 1074, 14719 본문

문제풀이/BAEKJOON Online Judge

[BAEKJOON] 1032, 1037, 1145, 1052, 1074, 14719

지수는말랑이 2023. 8. 28. 19:10
반응형

※ 소스코드는 각 문제 설명 하단에 <더보기>를 통해 확인하실 수 있습니다.

 

[bronze1, 1032 명령 프롬프트] - 단순 구현

파일 이름을 입력받을 때, 이름이 다른 부위를 ?로 변경한다

더보기
#include <iostream>
#include <cstring>
#pragma warning(disable:4996)
using namespace std;

char file_name[51];

int main() {
	int t;
	scanf("%d", &t);
	char name[51];
	scanf("%s", &file_name);
	int len = strlen(file_name);
	for (int i = 0; i < t-1; i++) {
		scanf("%s", &name);
		for (int j = 0; j < len; j++) {
			if (file_name[j] == '?') continue;
			if (file_name[j] != name[j]) {
				file_name[j] = '?';
			}
		}
	}
	printf("%s", file_name);
}

 

[bronze1, 1035 약수] - 정렬

가장 작은 약수와 가장 큰 약수를 곱하면 자기 자신이 나온다

더보기
#include <iostream>
#include <algorithm>

using namespace std;

/*
* 정렬
* 
* 모든 수의 최소 공배수를 구했을 때라 생각했지만, 자기 자신을 제외한 약수들의 집합이었다
*/

int ary[51];

bool ary_compare(int a, int b) {
	if (a > b) return true;
	else return false;
}

int main() {
	int ea = 0;
	scanf("%d", &ea);
	for (int e = 0; e < ea; e++) {
		scanf("%d", &ary[e]);
	}
	//sort(ary, ary + ea, greater<int>());
	sort(ary, ary + ea, ary_compare);

	printf("%d", ary[0] * ary[ea - 1]);
}

 

[bronze1, 1145 적어도 대부분의 배수] - 유클리드 호제법 + 조합

5개의 숫자 중 3개를 조합한 수에 대해 유클리드 호제법을 이용해 최대공약수와 최소공배수를 구하면된다

더보기
#include <iostream>

using namespace std;

/*
* 유클리드 호제법 + 조합
* 
* 문제의 적어도 세 개로 나뉘는 가장 자연수라는 말에서
* 4~5개를 확인할 때 더 작은 수가 나올 것이라 생각하여, 케이스를 추가했다가 시간초과가 났다
* 단순하게 생각하면 동일하지 않은 숫자가 하나 더 추가되는 것이니, 기대값의 최소가 추가하지 않은 경우랑 같으므로 3개의 수만 연산하면 됐다
*/

int ary[5];
int choice[3];
int len = 0;
int answer = INT32_MAX;

int gcd(int a, int b) {
	int c = a % b;
	while (c != 0) {
		a = b;
		b = c;
		c = a % b;
	}
	return b;
}
int lcm(int a, int b) {
	return (a * b) / gcd(a, b);
}

void make_set(int idx, int ea);
int calc_set();

int main() {
	for (int i = 0; i < 5; i++) {
		scanf("%d", &ary[i]);
	}
	make_set(0, 0);
	printf("%d", answer);
}

void make_set(int idx, int ea) {
	if (ea == 3) {
		int calc_res = calc_set();
		answer = answer < calc_res ? answer : calc_res;
		return;
	}
	for (int i = idx; i < 5; i++) {
		choice[ea] = ary[i];
		make_set(i + 1, ea + 1);
	}
}

int calc_set() {
	int big = 0, small = 0;
	big = max(choice[0], choice[1]);
	small = min(choice[0], choice[1]);
	
	int temp = lcm(big, small);
	big = max(temp, choice[2]);
	small = min(temp, choice[2]);
	
	return lcm(big, small);
}

 

[sliver1, 1052 물병] - 비트마스킹

2진수로 변환했을 때, 1의 값이 합쳐진 물병임을 파악해야 한다

c++에서 bitset을 이용해 1의 개수를 쉽게 파악할 수 있었고, N의 값을 1씩 늘리며 답을 찾아가면 됐다

더보기
#include <iostream>
#include <bitset>

using namespace std;

int main() {
	int N, K;
	scanf("%d %d", &N, &K);

	int result = N;
	while (true) {
		int cnt = bitset<32>(result).count();
		if (cnt <= K) break;
		result++;
	}
	printf("%d", result - N);
}

 

[sliver1, 1074 Z] - 분할정복

주어진 (r,c)가 분할정복할때 마다 몇 사분면에 속하는지 알아야한다
만약 N=1인 2x2 배열에서 (r,c)위치의 사분면을 알아내려 할 때,
1. 기준값은 2/2 = 1이되며
1-1. 각 사분면에 대해 1사분면(r<1&&c<1), 2사분면(r<1&&c>=1), 3사분면(r>=1&&c<1), 4사분면(r>=1&&c>=1)이 된다
2. Z형식으로 이루어짐에 따라, 각 사분면은 기준값의 배수가 시작 값이 된다
2-1. 각 사분면에 대해 1사분면(=(1-1)*1), 2사분면(=(2-1)*1), 3사분면(=(3-1)*1), 4사분면(=(4-1)*1)이 된다


즉, 기준값은 주어지는 N에 대해 2^(N-1)이며, 각 사분면의 값은 (현재 사분면-1)*기준값^2
3. 각 사분면에서 다시 사분면을 만들어 갈 때, (r,c)의 위치는 각 다른방법으로 변한다
3-1. 1사분면(그대로), 2사분면(c의 값이 기준값만큼 줄어듬), 3사분면(r의값이 기준값만큼 줄어듬), 4사분면(r,c의 값이 기준값만큼 줄어듬)
4. 분할 정복하는 사분면이 2x2 배열이 될 때 까지, 즉 N=0이 될 때 까지 반복한다.

 

재귀를 사용하는 경우 사분면을 지칭할 수 있는 값 2*(r%2)+(c%2)을 생각하고, (r,c)가 2배가 될 때마다 사분면 시작값이 4배로 확장되는 것을 깨달아야 한다

더보기
#include <iostream>
#include <cmath>

using namespace std;

/*
* 분할정복
* 
* 분할 정복하는 모든 구간에서 특정 위치와 사분면의 특징이 뚜렷하게 나타나는 문제에 적용할 수 있는 가장 기초적인 문제라고 생각한다
* 배열을 사분면으로 나누어, 위치를 찾아가는 행위까지는 생각했으나
* 그 사분면의 특정 위치를, 기준값으로 배열의 너비를 합해가는 행위는 생각하지 못했던 것이 아쉬웠다
* 
* 또한 (r,c)에 대해 각 사분면에서 새로운 사분면을 만들 때, 
* 각 사분면바다 해야하는 방식이 달랐던 점을 간과했고,
*/

int N, r, c;
int result;

int main() {
	scanf("%d %d %d", &N, &r, &c);

	while (N != 0) {
		int n = pow(2, --N);
		int res = 0;
		// (r, c)가 몇 사분면인지 알아야함
		if (r < n && c < n) { // 1사분면
			res = 0;
		}
		else if (r < n && c >= n) { // 2사분면
			res = 1;
			c -= n;
		}
		else if (r >= n && c < n) { // 3사분면
			res = 2;
			r -= n;
		}
		else if (r >= n && c >= n) { // 4사분면
			res = 3;
			r -= n;
			c -= n;
		}
		result += res * pow(n, 2);
	}
	printf("%d", result);
}

// -----  ----- ----- 재귀 -----  -----  ----- 
int recursive(int N, int r, int c) {
	if (N == 0) return 0;
	return 2 * (r % 2) + (c % 2) + 4 * recursive(N - 1, r / 2, c / 2);
}

int recursive_main() {
	scanf("%d %d %d", &N, &r, &c);
	recursive(N, r, c);
	printf("%d", result);
}

 

[gold5, 14719 빗물] - 시뮬레이션

현재 위치를 기준으로 왼쪽과 오른쪽의 가장 높은 블록을 찾아, 

그 중 낮은 블록의 높이와 현재 블록의 높이의 차를 빗물로 계산한다

더보기
#include <iostream>
#include <algorithm>

using namespace std;

/*
* 시뮬레이션
* 
* 특정 기준으로부터 다음으로 높은 블록의 위치를 찾아, 둘 사이에 고일 수 있는 빗물의 양을 찾으려 했었다
* 이 방법은 "다음으로 높은 블록의 위치를 찾는 것"에 많은 예외가 존재하고, 불확실하기 때문에 다른방법을 찾아야했다
*/

int H, W;
int world[501];
int main() {
	scanf("%d %d", &H, &W);
	for (int i = 0; i < W; i++) {
		scanf("%d", &world[i]);
	}
	int answer = 0;
	for (int i = 1; i < W - 1; i++) {
		int left = 0, right = 0;
		for (int j = i; j >= 0; j--) {
			if (world[i] <= world[j]) left = max(left, world[j]);
		}
		for (int j = i; j < W; j++) {
			if (world[i] <= world[j]) right = max(right, world[j]);
		}
		answer += abs(min(left, right) - world[i]);
	}
	printf("%d", answer);
}
반응형
Comments