굳건하게

안녕하세요.

여행벌입니다.

단순 구현 문제지만 깔끔하게 구현하고 싶어서 노력을 많이 했지만 실패한 문제입니다.

https://www.acmicpc.net/problem/2456

[알고리즘설계]

문제를 읽고 정말 단순히 구현합니다.

#include<iostream>
#include<algorithm>

using namespace std;

int ninput, total_score[4][3] = {};

bool cmp(int x, int y) {
	if (total_score[0][x] < total_score[0][y])
		return true;
	else if (total_score[0][x] > total_score[0][y])
		return false;
	else {
		if (total_score[1][x] < total_score[1][y])
			return true;
		else if (total_score[1][x] > total_score[1][y])
			return false;
		else {
			if (total_score[2][x] < total_score[2][y])
				return true;
			else
				return false;
		}
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> ninput;

	for (int i = 0; i < ninput; i++) {
		int input[3];
		for (int j = 0; j < 3; j++) {
			cin >> input[j];
			total_score[0][j] += input[j];
			total_score[4 - input[j]][j]++;
		}
	}

	int answer[3] = { 0,1,2 };
	sort(answer, answer + 3, cmp);

	if ( total_score[0][answer[1]] == total_score[0][answer[2]] &&
		total_score[1][answer[1]] == total_score[1][answer[2]] &&
		total_score[2][answer[1]] == total_score[2][answer[2]])
		cout << 0 << ' ' << total_score[0][answer[2]];
	else
		cout << answer[2]+1 << ' ' << total_score[0][answer[2]];
}

열심히 공부하고 노력하고 있는 꿈 많은 예비 개발자입니다.

혼자서 공부한 내용을 정리하고 포스팅하다 보니 틀린 내용이 있을 수도 있습니다.

많은 조언과 가르침 주실 분은 댓글로 자유롭게 남겨주셔도 좋을 것 같습니다! 

감사합니다.

안녕하세요.

여행벌입니다.

BOJ 2579 DP 문제인 계단오르기 풀이를 해보겠습니다.

https://www.acmicpc.net/problem/2579

[알고리즘설계]

2차원 배열 dp[2][N]을 선언해

[0][i] : i번 째 계단까지 오르는데 1칸을 점프해서 오를 때의 최대값. (i - 1번 째에서 올라온 경우)

[1][i] : i번 째 계단까지 오르는데 2칸을 점프해서 오를 때의 최대값. (i - 2번 째에서 올라온 경우)

(i - 1) 계단에서 점프하는 경우는 연속된 세 계단을 밟으면 안되므로,

2칸 점프해서 올라온 i-1의 최대값을 참조하고,

2칸 점프해서 i번 째 계단에 오른 경우의 최대 값은

1칸 점프해서 오른 i - 2 최대값과 2칸 점프해서 올라온 i - 2 최대값 중 더 큰 값을 참조합니다.

#include<iostream>
#include<algorithm>

using namespace std;

int input[301];

// list[x][y]
// y번째 계단에 (x+1)만큼 점프해서 온 최대값.
int list[2][301];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> input[i];
	list[0][1] = input[1];
	list[0][2] = input[1] + input[2];
	list[1][2] = input[2];

	for (int i = 3; i <= n; i++) {
		list[0][i] = list[1][i - 1] + input[i];
		list[1][i] = max(list[1][i - 2], list[0][i - 2]) + input[i];
	}
    cout << max(list[0][n], list[1][n]);

}

열심히 공부하고 노력하고 있는 꿈 많은 예비 개발자입니다.

혼자서 공부한 내용을 정리하고 포스팅하다 보니 틀린 내용이 있을 수도 있습니다.

많은 조언과 가르침 주실 분은 댓글로 자유롭게 남겨주셔도 좋을 것 같습니다! 

감사합니다.

안녕하세요.

여행벌입니다.

오늘은 대표적인 백트래킹 문제 LOTTO 풀이를 해보겠습니다.

https://www.acmicpc.net/problem/6603

[알고리즘풀이]

1. 백트레킹기법을 이용하여 k개의 수를 고르면 출력을 반복해줍니다.

#include<cstdio>
#include<vector>

using namespace std;

int list[12];

void printPicked(vector<int>& picked) {
	for (int i = 0; i < 6; i++)
		printf("%d ", list[picked[i]]);
	printf("\n");
}

void pick(int ninput, vector<int>& picked, int toPick) {
	if (toPick == 0) {
		printPicked(picked);
		return;
	}
	int smallest = picked.empty() ? 0 : picked.back() + 1;
	for (int next = smallest; next < ninput; next++) {
		picked.push_back(next);
		pick(ninput, picked, toPick - 1);
		picked.pop_back();
	}
}

int main(void) {
	while(1){
		int ninput;
		scanf("%d", &ninput);

		if (ninput == 0) {
			return 0;
		}

		for (int i = 0; i < ninput; i++)
			scanf("%d", &list[i]);

		for (int i = 0; i <= ninput - 6; i++) {
			vector<int> picked;
			picked.push_back(i);
			pick(ninput, picked, 5);
			picked.pop_back();
		}
		printf("\n");
	}
}

열심히 공부하고 노력하고 있는 꿈 많은 예비 개발자입니다.

혼자서 공부한 내용을 정리하고 포스팅하다 보니 틀린 내용이 있을 수도 있습니다.

많은 조언과 가르침 주실 분은 댓글로 자유롭게 남겨주셔도 좋을 것 같습니다! 

감사합니다.

안녕하세요.

여행벌입니다.

https://www.acmicpc.net/problem/9019

[알고리즘설계]

1. A에서 시작해서 명령어 D / S / L / R  을 한 숫자가 아직 방문하지 않은 숫자라면 queue에 담아 가며 B가 나올 때까지 BFS 탐색을 진행한다. 이때, int path[10000], char answer[10001] 을 이용해서 방문 경로를 저장한다.

2. B에서 다시 방문 경로를 역 탐색하며 출력해준다.

#include<iostream>
#include<queue>

using namespace std;

char DSLR[5] = "DSLR";
void BFS(int, int);

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int t;
	cin >> t;
	for (int i = 0; i < t; i++) {
		int A, B;
		cin >> A >> B;
		BFS(A,B);
	}
}

void BFS(int A, int B) {
	bool check[10000] = {};
	int npath[10000] = {};
	char cpath[10001] = {};
	queue<int> q;
	q.push(A);
	check[A] = true;
	while (!q.empty()) {
		int x = q.front(); q.pop();
		if (x == B) {
			vector<char>answer;
			while (x != A) {
				answer.push_back(cpath[x]);
				x = npath[x];
			}
			int length = (int)answer.size();
			for (int i = 0; i < length; i++)
				cout << answer[length - 1 - i];
			cout << '\n';
			return;
		}
		int list[4] = { (2 * x) % 10000, x - 1, (x % 1000) * 10 + x / 1000, (x % 10) * 1000 + x / 10 };
		if (list[1] < 0)
			list[1] = 9999;
		for (int i = 0; i < 4; i++) {
			if (!check[list[i]]) { // 지금 가려는 곳이 방문한 곳이 아니라면
				q.push(list[i]);
				check[list[i]] = true;
				npath[list[i]] = x;
				cpath[list[i]] = DSLR[i];
			}
		}

	}
}

코드는 간단하지만 구현하는데 정말 고생한 문제입니다...!

열심히 공부하고 노력하고 있는 꿈 많은 예비 개발자입니다.

혼자서 공부한 내용을 정리하고 포스팅하다 보니 틀린 내용이 있을 수도 있습니다.

많은 조언과 가르침 주실 분은 댓글로 자유롭게 남겨주셔도 좋을 것 같습니다! 

감사합니다.