굳건하게

안녕하세요.

여행벌입니다.

오늘은 예전부터 도전했으나.. 계속 실패를 하다 최근에 푼 백준 1011번 문제를 다뤄보겠습니다.

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

[알고리즘설계]

최소한이 점프 횟수로 도착해야 되므로, 우리는 점프 길이를 최대한 늘려야 합니다.

하지만, 마지막 점프는 다시 점프 길이 1로 돌아와야 되므로 점프해야 되는 길이 L이 주어졌을 때,

1 2 3 ⋯ N N-1 N-2 ⋯ 1 의 합이 L보다 작은 최대 N을 구해야 됩니다.

등차수열 합 공식을 이용해 보면 1 2 3 ⋯ N N-1 N-2 ⋯ 1 의 합은 N^2이 됩니다.

이때, 남은 L - N^2는 1 2 3 ⋯ N 으로 올라가는 과정에서 1 ~ N 길이의 점프가 다 가능하므로

가장 큰 N부터 점프 횟수를 추가해가며 남은 길이를 처리할 수 있습니다.

#include<iostream>

using namespace std;

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

	int t;
	cin >> t;
	for (int i = 0; i < t; i++) {
		long long x, y, length, point, count = 0;
		cin >> x >> y;
		length = y - x;
		if (length <= 3) {
			cout << length << '\n';
			continue;
		}
		for (point = 2; ; point++) {
			if (point * point > length) {
				point--;
				break;
			}
		}

		length -= point * point;
		count += 2 * point - 1;
		while (length != 0) {
			count += (length / point);
			length -= (length / point) * point;
			point--;
		}
		cout << count << '\n';
	}
}

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

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

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

감사합니다.

안녕하세요.

여행벌입니다.

문제만 보면 되게 어려워보이지만, Input이 작고 시간이 넉넉해서 무식하게 구현해도되는 문제입니다.

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

[알고리즘설계]

N번 째 숫자를 찾을때까지 666부터 무식하게 찾아본다.

#include<iostream>
#include<string>
using namespace std;

int main(void) {
	int ninput;
	bool flag = false;
	string temp;
	cin >> ninput;
	for (long long i = 666; ; i++) {
		flag = false;
		temp = to_string(i);
		for (int j = 0; j < temp.length() - 2; j++) {
			if (temp[j] == '6' && temp[j + 1] == '6' && temp[j + 2] == '6'){
				flag = true;
				break;
			}
		}
		if (flag)
			ninput--;
		if (ninput == 0){
			cout << i;
			break;
		}
	}
}

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

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

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

감사합니다.

안녕하세요.

여행벌입니다.

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

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]);

}

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

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

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

감사합니다.