코딩무식자 전공생

문제 출처: https://www.acmicpc.net/problem/14501

풀이

재귀함수 사용을 많이 어려워하는데, 아이디어는 알겠는데 구현력이부족해서 다른분들의 코드를 참고했습니다.

재귀함수를 사용하여 모든 케이스를 탐색해보는 방법을 사용했습니다.

나올수있는 경우는 1. 오늘 상담하고, 상담한 날만큼 건너뛰기 2. 상담안하고 하루 건너뛰기가 있습니다. 이것을 재귀로 구현해주면됩니다.

모든경우를 탐색하므로, 하루 건너뛰기를 수행하는 함수는 사실상 하루 이상의 day들을 건너뛴다고 할 수 있습니다.(이걸몰라서....)

코드

#include<iostream>
#include<algorithm>
using namespace std;
int t[16];
int p[16];
int n, max_val;
void func(int day,int profit);
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> t[i] >> p[i];
	//day=1일,이익0으로시작
	func(1, 0);
	cout << max_val << endl;
}
void func(int day,int profit)
{
	//탈출조건
	if (day > n + 1)return;
	//day==n+1이면max값 갱신후 종료(답)
	if(day==n+1)
	{
		max_val = max(max_val, profit);
		return;
	}
	//두가지 case

	//1. 오늘 상담하고,상담한 날만큼 건너뛰기
	if (day + t[day] <= n + 1)
	//두번째인자의, +p[day]해주는이유는 profit이 누적이고, p[day]가 그 날의 이익이므로
		func(day + t[day], profit+p[day]);
	//상담안하고 넘어간다.
	if (day + 1 <= n + 1)func(day + 1, profit);
}

결과

문제 출처: https://www.acmicpc.net/problem/14499

풀이

푸는데 2시간넘게걸린 문제입니다. 주사위가 돌아갈 때를 머릿속으로 그릴줄 알고 어느정도 공간감각력이 필요한 것 같습니다.

이 문제의 핵심은 주사위를 굴릴 때, 변화하는 주사위의 위치를 본인이 기준을 세워서 그 기준안에서 돌아가게끔 해야하는것입니다.

저는 문제에서 보기로 주어진 평면도를 기준으로삼았습니다.

즉, 보기의 평면도를 주사위로접으면, 아래 그림처럼 됩니다. 이 기준을 삼아서 최종적으로 dice[6](윗면)가 답으로 출력되게끔했습니다.

위의 평면도 상에서, 주사위를 동,서,남,북 방향으로 돌려보면, 규칙이 보입니다.(규칙이라기보단 당연한 내용입니다.)

동쪽, 서쪽 으로 돌리면, 2,5번 면은 움직이지 않고, 북쪽,남쪽으로 돌리면 3,4번 면은 움직이지않습니다.

이렇듯, 한번 돌리고 나서 변화하는 위치를 기억하기 위해 주사위의 복사본으로 변화하는 좌표를 담고, 기존 주사위를 변화할 수 있게 합니다.

이처럼, 본인이 삼은 위치의 변화의 기준을 이용하여 문제에 맞게 코드를 작성하면됩니다.

주의사항

이 부분 때문에 오래걸렸는데, 문제에서 지도의 좌표(r,c)는, 입력받을 (y,x)와 동일하기 때문에, x,y순이 아닌 y,x순으로 입력을 해야합니다.

(이걸로 틀리게하는건 좀 유치하다고생각하는데...)

코드

#include<iostream>
using namespace std;
int dice[7];
int temp[7];

int map[21][21];
int main()
{
	cin.tie(0);
	cin.sync_with_stdio(false);
	int n, m, y, x, k, call;
	cin >> n >> m >> y >> x >> k;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> map[i][j];
	
	for (int i = 0; i < k; i++)
	{
		cin >> call;
		if (call == 1)
		{
			if (x+1<m)
			{
				x = x + 1;
				temp[4] = dice[4];
				temp[1] = dice[1];
				temp[3] = dice[3];
				temp[6] = dice[6];


				dice[4] = temp[1];
				dice[1] = temp[3];
				dice[3] = temp[6];
				dice[6] = temp[4];
				if (map[y][x ] == 0)
				{
					map[y][x ] = dice[1];
				}
				else
				{
					dice[1] = map[y][x ];
					map[y][x ] = 0;
				}
				cout << dice[6] << endl;
			}
		}
		else if (call == 2)
		{
			if (x - 1 >= 0)
			{
				x = x - 1;
				temp[4] = dice[4];
				temp[1] = dice[1];
				temp[3] = dice[3];
				temp[6] = dice[6];


				dice[4] = temp[6];
				dice[1] = temp[4];
				dice[3] = temp[1];
				dice[6] = temp[3];
				if (map[y][x ] == 0)
				{
					map[y][x ] = dice[1];
				}
				else
				{
					dice[1] = map[y][x ];
					map[y][x ] = 0;
				}
				cout << dice[6] << endl;
			}		
		}
		else if (call == 3)
		{
			if (y - 1 >= 0)
			{
				y = y - 1;
				temp[2] = dice[2];
				temp[1] = dice[1];
				temp[5] = dice[5];
				temp[6] = dice[6];

				dice[2] = temp[6];
				dice[1] = temp[2];
				dice[5] = temp[1];
				dice[6] = temp[5];

					if (map[y][x] == 0)
					{
						map[y][x] = dice[1];
					}
					else
					{
						dice[1] = map[y][x ];
						map[y][x ] = 0;
					}
				cout << dice[6] << endl;
			}
		}
		else if (call == 4)
		{
			if (y + 1 <n)
			{
				y = y + 1;
				temp[2] = dice[2];
				temp[1] = dice[1];
				temp[5] = dice[5];
				temp[6] = dice[6];

				dice[2] = temp[1];
				dice[1] = temp[5];
				dice[5] = temp[6];
				dice[6] = temp[2];
				if (map[y][x] == 0)
				{
					map[y ][x] = dice[1];
				}
				else
				{
					dice[1] = map[y][x];
					map[y ][x] = 0;
				}
				cout << dice[6] << '\n';
			}
		}
	}
}

결과

문제 출처: https://www.acmicpc.net/problem/13458

풀이 

각 시험장에 총 감독관은 1명만 있어야하므로, 정답을 구할 때는 총감독관1명을 배치하고 남는 인원들에 대해서 부감독관을 구하는게 제일 빠릅니다. 

그렇기 때문에 그리디 알고리즘문제라고 할 수 있겠습니다.

길게  풀이를 적어내면 이해가 더 안갈 것같아 최대한 간략하게 풀이순서대로 작성해봤습니다.

1. ans는 int형이 아닌 longlong형으로 선언해야한다.

b,c가 1이고 각 시험장에 1,000,000씩 있으면 int형으로 표현불가

2. 총감독관부터 배치한다.

num[i]>=b, num[i]==b, num[i]<b일때 3가지 경우에 대해서 일단 연산해야함(그리디)

이 때, num[i]<b라면, 정답은 1이므로, 맨마지막 else문에 적어두고 위의 연산들만 신경쓰자. 

3. 총감독관을 구하고, 남은 인원들에 대해 부감독관을 구한다.

num[i]>=b, num[i]==b일 때 b를 구하고, 그 식 안에 c에 대해 똑같이 경우를 나누어서 구하자.

주의 사항

1. 조건 속 "b,c에 대해 (b>=1,c>=1)", "C는 여러명이 있을 수 있다." 를 C도 최소 한명있어야 한다로 해석하면안됨.

즉, 

인원 : 10

B: 10 , C: 10 일 때

B 1명, C 1명 이라고 해석하면 안됨. 테스트케이스 1번 결과를 참고해야한다. 

2. if문안에각 연산이 끝나고 다른 식을 실행하지않게 적절히 if문을 사용해야함. 이것만 주의하면 끝끝끝

코드

#include<iostream>
using namespace std;
int num[1000001];
int main()
{
	cin.tie(0);
	cin.sync_with_stdio(false);
	int n, b, c; 
	//long long 해야함
	long long ans = 0;
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> num[i];
	cin >> b >> c;
	for (int i = 1; i <= n; i++)
	{
		//num[i]가 b가관리할수있는인원보다많으면
		if (num[i] >=b)
		{
			//ex)10 10이면 
			if (num[i] == b)
			{
				//c가 최소 1이므로
				ans += 1;
			}
			//num[i]>b일 때
			else
			{
				//일단 총감독관은 무조건++해주고,
				ans++;
				//남는 인원에 대해서 부감독관구함
				num[i] -= b;
				
				//c에대해 연산
				if (num[i] <= c)
				{
					ans++;
					
				}
				//num[i]>c
				else
				{
					//짝수처리
					if (num[i] % c == 0)
					{
						ans += num[i] / c;
						
					}
					//홀수처리
					else
					{
						ans += num[i] / c + 1;
						
					}
				}
				
			}
		}
		//num[i]<b일때
		else
		{
			//총감독관한명만 배치하면됨.
		//주의!!: C도 한명추가되는게아님!!
			ans += 1;
		}
	}
	cout << ans << '\n';
}

결과