코딩묻은 디자이너

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

문제

돌 게임은 두 명이서 즐기는 재밌는 게임이다.

탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다.

두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1000)

출력

상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다.

​

풀이

두 사람이 "완벽"하게 플레이를 해야하는데 여기서 게임을 완벽하게 한다는게 어떤걸까 고민,,,

배스킨라빈스31 게임과 비슷한 전략으로 

마지막 돌을 가지기 위해서는 반드시 앞에 3개의 돌을 건너뛴 돌을 내가 가지고 있어야 한다

하지만 돌을 2개 선택할 수는 없다

분명 어떤 알고리즘을 적용할 수 있겠지만,,, 말이지,,, 그냥 홀수면 선공이 이기고 홀수면 후공이 이기게 설계가 된 게임인거시다아

코드

#include<iostream>
using namespace std;

int main()
{
	int N;
	cin >> N;
	if (N % 2 == 0)
	{
		cout << "CY";
	}
	else
	{
		cout << "SK";
	}
}

DFS(깊이우선탐색)와 BFS(너비우선탐색)

DFS(깊이우선탐색)

Depth First Search로 깊이를 우선으로 탐색한다.

- 최대한 내려간 후 더이상 탐색할 노드가 없는 경우 다시 돌아와 옆 노드 탐색

BFS(너비우선탐색)

Breadth First Search로 너비를 우선으로 탐색한다.

- 깊이가 1인 모든 노드 방문 후 다음 ㅍ깊이의 모든 노드 방문

백준 1260번 DFS와 BFS 파이썬 코드

def DFS(v):
    global visited
    visited[v] = 1
    print(v, end=' ')
    for i in range(len(arr[v])):
        if arr[v][i] == 1:
            if visited[i] == 0:
                DFS(i)

def BFS(v):
    global visited
    Q = [v]
    visited[v] = 1
    while Q:
        v = Q.pop(0)
        print(v, end=' ')
        for i in range(1, N+1):
            if visited[i] == 0 and arr[v][i] == 1:
                Q.append(i)
                visited[i] = 1

N, M, V = map(int,input().split())
arr = [[0]*(N+1) for _ in range(N+1)]
visited = [0]*(N+1)

for num in range(M):
    st, ed = map(int, input().split())
    arr[st][ed] = 1
    arr[ed][st] = 1
DFS(V)
print()
visited = [0]*(N+1)
BFS(V)

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

문제

666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워즈를 만들 때, 스타워즈 1, 스타워즈 2, 스타워즈 3, 스타워즈 4, 스타워즈 5, 스타워즈 6과 같이 이름을 지었고, 피터 잭슨은 반지의 제왕을 만들 때, 반지의 제왕 1, 반지의 제왕 2, 반지의 제왕 3과 같이 영화 제목을 지었다.

하지만 숌은 자신이 조지 루카스와 피터 잭슨을 뛰어넘는다는 것을 보여주기 위해서 영화 제목을 좀 다르게 만들기로 했다.

종말의 숫자란 어떤 수에 6이 적어도 3개이상 연속으로 들어가는 수를 말한다. 제일 작은 종말의 숫자는 666이고, 그 다음으로 큰 수는 1666, 2666, 3666, .... 과 같다.

따라서, 숌은 첫 번째 영화의 제목은 세상의 종말 666, 두 번째 영화의 제목은 세상의 종말 1666 이렇게 이름을 지을 것이다. 일반화해서 생각하면, N번째 영화의 제목은 세상의 종말 (N번째로 작은 종말의 숫자) 와 같다.

숌이 만든 N번째 영화의 제목에 들어간 숫자를 출력하는 프로그램을 작성하시오. 숌은 이 시리즈를 항상 차례대로 만들고, 다른 영화는 만들지 않는다.

입력

첫째 줄에 숫자 N이 주어진다. N은 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 N번째 영화의 제목에 들어간 수를 출력한다.

풀이

순서대로 나열해보면

666 1666 2666 3666 4666 5666 6660 6661 6662 6663 6664 6665 6666 6667 6668 6669 7666 8666 9666

로 진행된다 "666"이 들어있는지 확인하기 위해 문자열을 사용했다 

코드

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

int main()
{
	string davel = "666";
	int cnt = 0, N, ans = 0, i = 0;
	cin >> N;
	while (true)
	{
		i++;
		if (to_string(i).find(davel) != string::npos)
		{
			cnt++;
			ans = i;
			//cout << cnt << "번 째 작은수" << ans << endl;
			if (cnt == N)
			{
				break;
			}
		}

	}
	cout << ans;
}

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

문제

입력 받은 대로 출력하는 프로그램을 작성하시오.

입력

입력이 주어진다. 입력은 최대 100줄로 이루어져 있고, 알파벳 소문자, 대문자, 공백, 숫자로만 이루어져 있다. 각 줄은 100글자를 넘지 않으며, 빈 줄이 주어질 수도 있고, 각 줄의 앞 뒤에 공백이 있을 수도 있다.

출력

입력받은 그대로 출력한다.

풀이

브론즈 1 이지만 그렇게 어렵지 않다

string 의 getline 을 쓸 수 있는가를 묻는 문제였다

코드

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

int main()
{
	string text;
	for (int i = 0; i < 100; i++)
	{
		getline(cin, text);
		cout << text << endl;
	}

}

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

문제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

풀이

유클리스 호제법을 사용하여 풀이

코드

#include<iostream>
using namespace std;

int main()
{
	int a, b, c, d;
	cin >> a >> b;
	c = a % b;
	d = a * b;
	while (c > 0)
	{
		a = b;
		b = c;
		c = a % b;
	}
	cout << b << '\n' << d / b;
}

문제

세준이는 학교에서 집으로 가려고 한다. 도시의 크기는 무한대이고, 도시의 세로 도로는 모든 정수 x좌표마다 있고, 가로 도로는 모든 정수 y좌표마다 있다. 세준이는 현재 (0, 0)에 있다. 그리고 (X, Y)에 위치한 집으로 가려고 한다. 세준이가 걸을 수 있는 방법은 두가지 인데, 하나는 도로를 따라서 가로나 세로로 한 블록 움직여서 이번 사거리에서 저 사거리로 움직이는 방법이고, 블록을 대각선으로 가로지르는 방법이 있다.

세준이가 집으로 가는데 걸리는 최소시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 집의 위치 X Y와 걸어서 한 블록 가는데 걸리는 시간 W와 대각선으로 한 블록을 가로지르는 시간 S가 주어진다. X와 Y는 1,000,000,000보다 작거나 같은 음이 아닌 정수이고, W와 S는 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 세준이가 집에가는데 걸리는 최소시간을 출력한다.

풀이

부르트포스알고리즘 문제로 무식하게 경우의 수를 모두 나열해 풀었다

오버플로우가 발생해서 고생고생 했다.

요 부분 공부가 더 필요한 것 같다. 자료형에 대해 더 알아봐야지이

2022.03.03 - [study] - 항은 2개의 인수를 받아드리는 함수로 계산되지 않습니다

마주친 오류

실버5라며!!!

코드

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

int main()
{
	long long X, Y, W, S, ans_1 = 0, ans_2 = 0, ans_3 = 0;
	cin >> X >> Y >> W >> S;
	// 직선으로만
	ans_1 = (X + Y) * W;
	//if (ans < min_ans) min_ans = ans;

	// 대각선으로만
	ans_2 = (((max(X,Y))-((X+Y)%2))*S)+(((X+Y)%2)*W);
	//if (ans < min_ans) min_ans = ans;

	// 대각선 가고 남은거
	ans_3 = (min(X,Y) * S) + ((max(X,Y)-min(X,Y)) * W);
	//if (ans < min_ans) min_ans = ans;

	cout << min(ans_1, min(ans_2, ans_3));
}

실패의 흔적을 고이고이 남긴 코드

C2064 항은 2개의 인수를 받아들이는 함수로 계산되지 않습니다.

평소에는 min 혹은 max를 비교할 때 ans_min과 ans를 두고 둘을 비교하며 변경하는 식으로 계산하는걸 선호하는데

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

자료형이 long이구,,, ans_min을 무슨 값을 디폴트 값으로 둬야하는지 감이 안잡혀서

ans_1

ans_2

ans_3 이런 식으로 값들을 구한 후 이 중에서 가장 작은 값을 구하기 위해

min(ans_1, ans_2, ans_3)을 사용했는데

'항은 2개의 인수를 받아들이는 함수로 계산되지 않습니다.' 라는 오류가 발생했다. 몬말이지...

template <class _Ty, class _Pr>
_NODISCARD constexpr const _Ty&(min)(const _Ty& _Left, const _Ty& _Right, _Pr _Pred) noexcept(
    noexcept(_Pred(_Right, _Left))) /* strengthened */ {
    // return smaller of _Left and _Right
    return _Pred(_Right, _Left) ? _Right : _Left;

오류를 클릭해서 min 탬플릿에 들어가보니...

_Right, _Left로 2개의 항만 비교를 한다는걸 알 수 있었다.

파이썬에서 넘어온 나에게 이것은 너무 가혹해,,,구냥 젤 작은거 출력해달라,,,

cout << min(ans_1, min(ans_2, ans_3));

일단 꼼수로 이런식으로 해결했다!

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

문제

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.

<그림 1>

예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.

<그림 2>

계단 오르는 데는 다음과 같은 규칙이 있다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

입력

입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

출력

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

풀이

2칸 이상 넘을 수 없기 때문에 지금 현재 계단에서의 값을 구하기 위해서는 누적값과 직전값이 2가지 이다.

결론은

이렇게 생각하니 간단하게 풀 수 있었다!

코드

#include<iostream>
using namespace std;
#define MAX 301

int main()
{
	int score[MAX];
	int ans_list[MAX];
	int N;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> score[i];
	}
	ans_list[0] = score[0];
	ans_list[1] = score[0] + score[1];
	ans_list[2] = max(score[0] + score[2], score[1] + score[2]);

	for (int i = 3; i < N; i++)
	{
		//값을 더할 때 필요한 값은 바로 앞에 어떤 수였는지, 그것과 더해지는 누적값이 무엇인지
		ans_list[i] = max(ans_list[i - 3] + score[i] + score[i-1], ans_list[i - 2] + score[i]);
	}
	cout << ans_list[N - 1];
}

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

문제

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여섯 가지이다.

• push X: 정수 X를 큐에 넣는 연산이다.
• pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 큐에 들어있는 정수의 개수를 출력한다.
• empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
• front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

풀이

2022.03.01 - [study/백준] - [백준] 10828. 스택 : C++

과 같은 방법으로 풀이했다.

스택과 다르게 큐의 경우 pop을 하면 가장 앞의 정수가 사라진다

코드

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

int main()
{
	int N;
	cin >> N;
	queue<int>arr;

	for (int i = 0; i < N; i++)
	{
		string commend;
		cin >> commend;
		// 문자열로 비교
		if (commend == "push")
		{
			int num;
			cin >> num;
			arr.push(num);
		}
		else if (commend == "pop")
		{
			// 비어있는경우 -1 출력
			if (arr.empty() == true) cout << "-1" << endl;
			else
			{
				// 가장 앞에 있는 정수 출력 후 삭제
				cout << arr.front() << endl;
				arr.pop();
			}

		}
		else if (commend == "size")
		{
			// 사이즈 출력
			cout << arr.size() << endl;
		}
		else if (commend == "empty")
		{
			// 비어있는 경우 1 숫자가 있는 경우 0
			if (arr.empty() == true) cout << "1" << endl;
			else cout << "0" << endl;
		}
		else if (commend == "front")
		{
			// 비어있는 경우 -1 그렇지 않은 경우 가장 앞의 수 출력
			if (arr.empty() == true) cout << "-1" << endl;
			else cout << arr.front() << endl;
		}
		else
		{
			// 가장 뒤에 수 출력
			if (arr.empty() == true) cout << "-1" << endl;
			else cout << arr.back() << endl;
		}
	}
}

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

문제

정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 다섯 가지이다.

• push X: 정수 X를 스택에 넣는 연산이다.
• pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 스택에 들어있는 정수의 개수를 출력한다.
• empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
• top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

풀이

입력받은 명령어를 문자열로 비교하여 하나하나 처리하였다

코드

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

int main()
{
	int N;
	cin >> N;
	stack<int>arr;
	for (int i = 0; i < N; i++)
	{
		string commend;
		cin >> commend;
		// 입력받은 commend와 문자열 비교
		if (commend == "push")
		{
			int num;
			cin >> num;
			arr.push(num);
		}
		else if (commend == "pop")
		{	
			// stack이 비어있는 경우 -1을 출력
			if (arr.empty() == true)
			{
				cout << "-1" << endl;
			}
			else
			{
				// 가장 위에 있는 정수 출력 후 pop으로 빼기
				cout << arr.top() << endl;
				arr.pop();
			}
			
		}
		else if (commend == "size")
		{
			// 사이즈 출력
			cout << arr.size() << endl;
		}
		else if (commend == "empty")
		{
			// 비어있는지 여부 확인
			if (arr.empty() == true)
			{
				cout << "1" << endl;
			}
			else cout << "0" << endl;
		}
		else
		{
			if (arr.empty() == true)
			{
				cout << "-1" << endl;
			}
			else cout << arr.top() << endl;
		}
	}
}