취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 28065번 문제인 SW 수열 구하기이다.
문제는 아래 링크를 확인하자.

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

1부터 시작해 지금까지 사용하지 않은 가장 차가 큰 수를 반복해 나열해 얻을 수 있는 수열을 생각해보자. 이 수열의 계차의 절댓값을 나열하면 N-1, N-2, N-3, ..., 1과 같이 단조감소하는 것을 알 수 있다. 이는 문제에서 요구하는 성질을 만족하므로 이 수열은 문제의 답 중 하나가 된다.

위와 같은 수열을 생성하는 코드를 작성해 문제를 해결하자. 사용하지 않은 수 중 가장 큰 수 및 가장 작은 수를 탐색하는 \(O(N)\) 알고리즘을 이용해도 제한시간 내로 충분히 문제를 해결할 수 있다. 아래와 같이 다음 가장 큰 수 및 가장 작은 수를 저장하는 L, R과 같은 변수를 이용해도 좋다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N;
int L, R;

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

	cin >> N;
	L = 1, R = N;
	for (; L < R; L++, R--) cout << L << ' ' << R << ' ';
	if (L == R) cout << L;
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 28064번 문제인 이민희진이다.
문제는 아래 링크를 확인하자.

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

두 이름 s1과 s2가 있을 때, 두 이름이 연결가능한지를 판단할 수 있다면 이를 N(N-1)/2가지 순서쌍에 적용해보는 것으로 문제를 해결할 수 있을 것이다. 이 판단방법을 생각해보자.

두 문자열의 공통 부분 길이 len이 될 수 있는 정수는 1 이상 min(s1의 길이, s2의 길이) 이하이다. 각 후보 len에 대하여 s1의 앞 len개 문자로 구성된 문자열과 s2의 뒷 len개 문자로 구성된 문자열이 같은지, 그리고 s2의 앞 len개 문자로 구성된 문자열과 s2의 앞 len개 문자로 구성된 문자열이 같은지를 각각 확인해 하나라도 같아면 두 문자열을 이어붙일 수 있음을 알 수 있다. 또한 그렇지 않다면 이어붙일 수 없음을 알 수 있다. 이를 이용해 문제를 해결하자.

아래는 제출한 소스코드이다.

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

int N;
string s[100];

int ans;

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

	cin >> N;
	for (int i = 0; i < N; i++) cin >> s[i];

	for (int i = 0; i < N; i++) {
		string& s1 = s[i];
		int s1len = s1.length();
		for (int j = i + 1; j < N; j++) {
			string& s2 = s[j];
			int s2len = s2.length();
			int len = min(s1len, s2len);
			bool chk = 0;
			for (int l = 1; l <= len; l++) {
				if (s1.substr(0, l) == s2.substr(s2len - l, l)) chk = 1;
				if (s2.substr(0, l) == s1.substr(s1len - l, l)) chk = 1;
			}

			if (chk) ans++;
		}
	}

	cout << ans;
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 28063번 문제인 동전 복사이다.
문제는 아래 링크를 확인하자.

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

동전의 초기 위치가 왼쪽 변에 맞닿아있다면 기계를 왼쪽으로 조작할 필요가 없고 그렇지 않다면 기계를 왼쪽으로 조작해야 함을 관찰하자.

이는 다른 변들과 대응되는 방향에 대하여 동일하게 적용된다. 이를 이용해 문제의 답을 구하는 코드를 작성해 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N, x, y;
int ans = 4;

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

	cin >> N >> x >> y;
	if (x == 1) ans--;
	if (x == N) ans--;
	if (y == 1) ans--;
	if (y == N) ans--;

	cout << ans;
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 28062번 문제인 준석이의 사탕 사기이다.
문제는 아래 링크를 확인하자.

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

가게에 있는 사탕 개수의 총합이 짝수개이면 모든 사탕을 구입하는 것이 최선임은 자명하다.

그렇지 않다면 사탕 개수가 홀수인 사탕 묶음이 적어도 하나 이상 존재한다. 그 중 가장 개수가 적은 묶음 하나를 제외한 모든 사탕을 구입하는 것이 최선의 방법이 된다.

위 내용을 구현한 코드를 작성해 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N;
int ans, oddmin = 1000000007;

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

	cin >> N;
	while (N--) {
		int x; cin >> x;
		ans += x;
		if (x & 1) oddmin = min(oddmin, x);
	}

	if (ans & 1) cout << ans - oddmin;
	else cout << ans;
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 28061번 문제인 레몬 따기이다.
문제는 아래 링크를 확인하자.

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

x=i에 위치한 레몬나무에서 레몬을 딸 경우 집까지 2번 행동(이동)을 N-i+1회 하므로 집에 들고 가게 되는 레몬의 개수는 \(max(a_i-(N-i+1),0)\)과 같게 된다.

각 레몬나무마다 위의 값을 계산해 그 중 가장 큰 값을 구하는 것으로 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N, ans;

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

	cin >> N;
	for (int i = 1; i <= N; i++) {
		int x; cin >> x;
		ans = max(ans, x - (N - i + 1));
	}

	cout << ans;
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 28281번 문제인 선물이다.
문제는 아래 링크를 확인하자.

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

X의 값은 변하지 않으므로, 문제에서 구하는 값을 최소화하기 위해서는 "붙어있는 두 양말가격의 합"을 최소화해야 함을 알 수 있다.

양말의 가격을 배열에 저장해두고 반복문을 이용해 인접한 두 값의 합을 전수조사해 "붙어있는 두 양말가격의 합"을 계산하고 문제를 해결하자. 배열을 사용하지 않고 해결하는 풀이 또한 존재하는데, 이를 생각하는 것은 읽는이에게 맡긴다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N, X;
int arr[100000];
int mn = 1000000007;

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

	cin >> N >> X;
	for (int i = 0; i < N; i++) cin >> arr[i];
	N--;
	for (int i = 0; i < N; i++) mn = min(mn, arr[i] + arr[i + 1]);

	cout << mn * X;
}