말랑한 하루

[BAEKJOON] 1524, 1672, 1813, 1262, 1276, 1038 본문

문제풀이/BAEKJOON Online Judge

[BAEKJOON] 1524, 1672, 1813, 1262, 1276, 1038

지수는말랑이 2023. 8. 31. 23:00
반응형

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

 

[bronze1, 1524 세준세비] - 구현

간단한 정렬 및 비교를 진행하면 된다.

세비의 병사가 세준과 같을 때, 세비의 병사가 진다는 것에 유의한다

더보기
#include <iostream>
#include <algorithm>
#pragma warning(disable:4996)

using namespace std;

int sejoon[1000001];
int sebi[1000001];
int main() {
	int tc;
	scanf("%d", &tc);
	for (int t = 0; t < tc; t++) {
		int N, M;
		scanf("%d %d", &N, &M);
		for (int n = 0; n < N; n++) scanf("%d", &sejoon[n]);
		for (int m = 0; m < M; m++) scanf("%d", &sebi[m]);
		sort(sejoon, sejoon + N);
		sort(sebi, sebi + M);

		int n = 0, m = 0;
		while (n != N && m != M) {
			if (sejoon[n] >= sebi[m]) m++;
			else n++;
		}
		n == N ? printf("B\n") : printf("S\n");
	}
}

 

[bronze1, 1672 DNA 해독] - 구현

문자열의 끝부터 처음까지 해독판을 활용해 치환하며 결과값을 찾아가면 된다

해독판을 행렬로 표현할 지, 케이스별로 직접 구현할 지 선택이지만

문자열의 최대 길이가 백만이므로 직접구현이 가능했다

문자열의 끝 중 어느부분을 기준으로 잡을 지, 어떤 곳에 결과를 저장하면서 진행할 지 헷갈리지 않도록 하자

더보기
#include <iostream>
#pragma warning(disable:4996)

using namespace std;

int N;
char str[1000001];

char board[4][4] = {
	{'A', 'C', 'A', 'G'},
	{'C', 'G', 'T', 'A'},
	{'A', 'T', 'C', 'G'},
	{'G', 'A', 'G', 'T'}
};

int decrypt(char a) {
	switch (a) {
	case 'A':
		return 0;
	case 'G':
		return 1;
	case 'C':
		return 2;
	case 'T':
		return 3;
	}
}

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

	if (N == 1) {
		printf("%c", str[0]);
		return 0;
	}
	for (int i = N - 2; i >= 0; i--) {
		str[i] = board[decrypt(str[i])][decrypt(str[i + 1])];
		printf("%c\n", str[i]);
	}

	printf("%c", str[0]);
}

 

 

[bronze1, 1813 논리학 교수] - 애드 혹(Ad-Hoc)

'i개의 말은 참이다'라는 N번의 말이 주어질 때, i개가 참이라 말한 N의 개수가 동일할 때가 정답이된다

문제에서 언급된 대로, 내용이 모순된 말은 '0개의 말은 참이다'임에 주의한다

더보기
#include <iostream>
#pragma warning(disable:4996)

using namespace std;

int N, answer = -1;
int board[51];
int cnt[51];
int main() {
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &board[i]);
		cnt[board[i]]++;
	}
	if (N == 1 && board[0] == 0) {
		printf("-1");
		return 0;
	}
	for (int i = 0; i <= N; i++) {
		if (i == cnt[i]) answer = i;
	}
	printf("%d", answer);
}

 

[sliver1, 1262 알파벳 다이아몬드] - 구현

반복값인 H만큼 (r,c) 좌표를 압축한다 생각해야 한다
중심부는 (N-1, N-1)이므로, 중심부와의 거리가 N-1이하면 알파벳, 초과면 .이다
알파벳은 a-z까지 완료 후, 다시 a로 반복되는 것에 유의한다

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

int main() {
	int N, R1, R2, C1, C2;
	scanf("%d %d %d %d %d", &N, &R1, &C1, &R2, &C2);
	int H = (N - 1) * 2 + 1;
	for (int r = R1; r <= R2; r++) {
		for (int c = C1; c <= C2; c++) {
			int nr = r % H;
			int nc = c % H;
			int dist = abs(N - 1 - nr) + abs(N - 1 - nc);
			printf("%c", dist <= N - 1 ? 'a' + dist % 26 : '.');
		}
		printf("\n");
	}
}

 

[sliver1, 1276 PLATFORME] - 구현

처음에는 플랫폼의 1)시작점을 기준으로 정렬하여, 첫 플랫폼과 두번째 플랫폼이 2)교차하는지 확인하고 3)둘의 높이차에 따라 4)기둥의 수를 더해가는 방식으로 풀이했다

하지만 플랫폼이 겹쳐지지않게 주어지는 경우만 주어지지만, 내 코드의 무엇이 하자가 있었는지 4%에서 웃돌았다

그래서 풀이방법을 예시와 같게, 적은 높이의 플랫폼의 기둥부터 세우고, 기둥이 세워진곳은 플랫폼의 고도를 저장하며 해결했다

플랫폼의 시작과 끝은 좌표계로 주어지나, 실제 다리가 놓아지는 것은 좌표와 좌표 사이에 놓이기 때문에 코드상 겹치는 부분에 유념하라. 필자는 끝 좌표계의 값을 1 감소시켜 처리했다

더보기
#include <iostream>
#include <algorithm>
#pragma warning(disable:4996)

using namespace std;

struct Flatforme {
	int h, fs, se;
};
bool flatformeCompare(Flatforme a, Flatforme b) {
	return a.h < b.h;
}

Flatforme flatforme[101];
int bar[10001];

int main() {
	int N;
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		int h, fs, se;
		scanf("%d %d %d", &h, &fs, &se);
		flatforme[i] = { h, fs, se - 1 };
	}
	sort(flatforme, flatforme + N, flatformeCompare);

	int answer = 0;
	for (int i = 0; i < N; i++) {
		answer += flatforme[i].h * 2 - (bar[flatforme[i].fs] + bar[flatforme[i].se]);
		for (int b = flatforme[i].fs; b <= flatforme[i].se; b++) {
			bar[b] = flatforme[i].h;
		}
	}
	printf("%d", answer);
}

 

[gold5, 1038 감소하는 수] - 재귀, 백트래킹

0~9를 활용해 감소하는 수를 만들 때,
몇개의 숫자를 활용해 뽑아도 만들 수 있는 감소하는 수는, 오름차순으로 정렬된 1개 뿐이다
따라서 10개를 활용해 만들 수 있는 감소하는 수의 갯수는 최대 2^10-1 = 1023개이며, 이 이상의 수는 감소하는 수가 될 수 없다
이를 활용해 10개의 숫자를 조합하여 1023개의 감소하는 수를 만들어 놓고, 정렬한 뒤 답을 찾아내는 방법으로 활용할 수 있다

더보기
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#pragma warning(disable:4996)

using namespace std;

#define ll long long

vector<ll> decrease;

int len = 0;

void makeDecreaseNumber(int pivot, ll num, int cnt) {
	if (cnt == len) {
		decrease.push_back(num);
		return;
	}
	for (int i = pivot; i >= 0; i--) {
		makeDecreaseNumber(i - 1, num * 10 + i, cnt + 1);
	}
}

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

	for (int i = 1; i <= 10; i++) {
		len = i;
		makeDecreaseNumber(9, 0, 0);
	}
	sort(decrease.begin(), decrease.end());

	printf("%lld", decrease.size() > N ? decrease[N] : -1);
}
반응형
Comments