말랑한 하루
[BAEKJOON] 1032, 1037, 1145, 1052, 1074, 14719 본문
※ 소스코드는 각 문제 설명 하단에 <더보기>를 통해 확인하실 수 있습니다.
[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);
}
'문제풀이 > BAEKJOON Online Judge' 카테고리의 다른 글
[BAEKJOON] 1292, 1296, 1356, 1141, 1189, 9251 (0) | 2023.08.30 |
---|---|
[BAEKJOON] 1236, 1259, 1268, 1080, 1124, 2493 (0) | 2023.08.29 |
[BAEKJOON] 1541 잃어버린 괄호 (Python) (0) | 2022.10.29 |
[BAEKJOON] 1181 단어 정렬 (Java) (0) | 2022.10.29 |
[BAEKJOON] 1157 단어공부 (Java) (0) | 2022.10.29 |