[BAEKJOON] 1292, 1296, 1356, 1141, 1189, 9251

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

 

[bronze1, 1292] - 구현

배열의 수를 1001로 정확히 잡을 시, OutOfBounds 런타임에러가 뜬다
등차로 증가하는 idx를 n번 반복하기 때문이므로 넉넉히 2001이상 잡아주도록 하자

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

int A, B, ary[1001];
int main() {
	scanf("%d %d", &A, &B);
	int idx = 1;
	
	for (int i = 1; i <= B;) {
		for (int k = 0; k < idx; k++) {
			ary[i++] = ary[i - 1] + idx;
		}
		idx++;
	}
	printf("%d", ary[B] - ary[A - 1]);
}

 

[bronze1, 1296] - 문자열 + 구현

이현이가 만든 공식에 집중할 것.
문제를 잘못읽고 연두의 이름과 팀 이름을 대조하여 새로운 공식을 만들어 가며 헤맸음

#include <iostream>
#include <string>
#pragma warning(disable:4996)

using namespace std;

int yondu[4];
int N, answer = -1;
string team;

int probability(int ehwan[]);

int main() {
	string name;
	cin >> name;
	for (int i = 0; i < name.length(); i++) {
		switch (name[i]) {
		case 'L':
			yondu[0]++;
			break;
		case 'O':
			yondu[1]++;
			break;
		case 'V':
			yondu[2]++;
			break;
		case 'E':
			yondu[3]++;
			break;
		}
	}
	cin >> N;

	for (int n = 0; n < N; n++) {
		cin >> name;
		int ehwan[4] = { 0, };
		for (int i = 0; i < name.length(); i++) {
			switch (name[i]) {
			case 'L':
				ehwan[0]++;
				break;
			case 'O':
				ehwan[1]++;
				break;
			case 'V':
				ehwan[2]++;
				break;
			case 'E':
				ehwan[3]++;
				break;
			}
		}
		int res = probability(ehwan);
		if (answer <= res) {
			if (answer == res) {
				if (team > name) {
					team = name;
				}
			}
			else {
				team = name;
			}
			answer = res;
		}
	}
	cout << team;
}

int probability(int ehwan[]) {
	int ary[4] = { 0, };
	for (int i = 0; i < 4; i++) ary[i] = yondu[i] + ehwan[i];
	int res = 1;
	for (int i = 0; i < 4; i++)
		for (int j = i + 1; j < 4; j++) {
			res *= (ary[i] + ary[j]);
		}
	return res % 100;
}

[bronze1, 1356] - 문자열 + 구현

#include <iostream>
#include <string>
#pragma warning(disable:4996)

using namespace std;

int main() {
	string num;
	cin >> num;
	if (num.length() == 1) {
		printf("NO");
		return 0;
	}

	for (int k = 1; k < num.length(); k++) {
		int left = 1, right = 1;
		for (int i = 0; i < k; i++) {
			left *= num[i] - '0';
		}
		for (int j = k; j < num.length(); j++) {
			right *= num[j] - '0';
		}
		if (left == right) {
			printf("YES");
			return 0;
		}
	}
	printf("NO");
}

[sliver1, 1141] - 문자열 + 구현

겹치지 않고 다른단어의 접두어를 판단할 수 있는 좋은 방법은,
다른단어의 접두어가 될 수 있는 짧은 단어를 먼저 비교하는 것이다
 
짧은 단어부터 누군가의 접두어가 되지 않는 부분집합을 만들고
그 부분집합 내 단어가, 다른단어의 접두어가 되는지 판단하고 개수를 줄여나가면 된다.
단, 개수를 줄여나갈 때 집합에는 같은 단어가 두번이상 있을 수 있음에 유의한다

#include <iostream>
#include <algorithm>
#include <string>
#pragma warning(disable:4996)

using namespace std;

int N;
int answer;
string word[51];
bool word_compare(string a, string b) {
	for (int i = 0; i < a.length(); i++)
		if (a[i] != b[i]) return false;
	return true;
}
bool len_compare(string a, string b) {
	return a.length() < b.length();
}
int main() {
	scanf("%d", &N);
	for (int n = 0; n < N; n++) {
		cin >> word[n];
	}
	sort(word, word + N, len_compare);
	for (int i = 0; i < N; i++) {
		int cnt = 1;
		for (int j = i + 1; j < N; j++) {
			if (!word_compare(word[i], word[j])) cnt++;
			for (int k = j + 1; k < N; k++) {
				if (word_compare(word[j], word[k])) {
					cnt--;
					break;
				}
			}
		}
		answer = answer > cnt ? answer : cnt;
	}
	cout << answer;
}

 

[sliver1, 1189] - 재귀, 백트래킹

간단한 DFS문제이다

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

using namespace std;

int R, C, K, answer;
char map[6][6];
bool visit[6][6];

int dr[] = { -1,1,0,0 };
int dc[] = { 0,0,-1,1 };
bool range(int r, int c) {
	return r < 0 || c<0 || r>R - 1 || c>C - 1 || map[r][c] == 'T' || visit[r][c];
} 
void comeBackHome(int r, int c, int cnt);

int main() {
	scanf("%d %d %d", &R, &C, &K);
	for (int r = 0; r < R; r++) {
		scanf("%s", &map[r]);
	}
	visit[R - 1][0] = true;
	comeBackHome(R-1, 0, 1);
	printf("%d", answer);
}

void comeBackHome(int r, int c, int cnt) {
	if (r == 0 && c == C - 1) {
		if (cnt == K) answer++;
		return;
	}
	for (int d = 0; d < 4; d++) {
		int nr = r + dr[d];
		int nc = c + dc[d];
		if (!range(nr, nc)) {
			visit[nr][nc] = true;
			comeBackHome(nr, nc, cnt + 1);
			visit[nr][nc] = false;
		}
	}
}

 

[gold1, 9251] - LCS(최장공통부분수열)

첫번째 행과 열을 0으로 맞추고, 이후 기준이 되는 열에 행의 문자를 넣고, 문자가 일치하면 행렬값에 1을 더한다
행 테이블의 값은 이전 테이블 값의 누적된 값이 기록되며, 새롭게 매칭되는 문자가 나왔을 때 다음을 생각한다

1) 현재 서로다른 문자열인 경우, 현재 테이블에 들어갈 수는 (왼쪽or위쪽중 큰 값)을 따라간다
2) 현재 서로같은 문자열인 경우, 현재 테이블에 들어갈 수는 (왼쪽위 대각선 값 + 1)이다
위 구현과정을 숙지하고 있다면 어렵지 않은 문제다.

#include <iostream>
#include <string>
#pragma warning(disable:4996)

using namespace std;

string R, C;
int LCS[1001][1001];
int answer;

int main() {
	cin >> C;
	cin >> R;

	R = "0" + R;
	C = "0" + C;

	int r_len = R.length();
	int c_len = C.length();

	for (int r = 0; r < r_len; r++) {
		for (int c = 0; c < c_len; c++) {
			if (r == 0 || c == 0) {
				LCS[r][c] = 0;
				continue;
			}
			if (C[c] == R[r]) {
				LCS[r][c] = LCS[r - 1][c - 1] + 1;
			}
			else {
				LCS[r][c] = max(LCS[r - 1][c], LCS[r][c - 1]);
			}
		}
	}
	cout << LCS[r_len - 1][c_len - 1];
}