슥지니의 코딩노트

문제 링크: https://www.acmicpc.net/problem/15489

<문제 풀이> 다이나믹 프로그래밍(DP), 수학

파스칼 삼각형을 아래 그림과 같이 왼쪽으로 정렬된 형태로 생각하면 2차원 배열로 쉽게 표현할 수 있습니다.

그러면 맨 왼쪽을 모두 1로 채운 뒤 ㄱ자 모양으로 파스칼 삼각형 DP 배열을 채우면 됩니다.

<C++소스코드>

문제 링크: https://www.acmicpc.net/problem/16953

<문제 풀이>  BFS 알고리즘

큐에 다음 두 가지를 삽입하는 BFS를 구현하면 되는 문제입니다.

1. cur * 2 

2. cur * 10 + 1 

큐가 비워지기 전에 A == B가 되는 수를 찾으면 성공이고 큐가 비워졌을 때 A == B가 되는 수를 못 찾으면 실패입니다.

숫자 맨 뒤에 1을 추가하는 것은 2로 나누어 떨어지지 않기 때문에 숫자에 2를 곱한 것과 중복되지 않습니다.

따라서 방문 체크 배열을 만들 필요가 없습니다.

숫자는 최대 10^9이므로 2번 연산에서 10^9 * 10 + 1을 하면 int의 최대 크기를 넘어가기 때문에 long long 자료형을 사용해야 합니다.

<C++소스코드>

문제 링크: https://www.acmicpc.net/problem/11508

<문제 풀이> 그리디 알고리즘

최대한 비싼 가격을 무료로 지불해야 하므로 내림차순으로 정렬해서 인덱스를 3으로 나누었을 때 나머지가 2인 가격을 무시하면 됩니다.

<C++소스코드>

문제 링크: https://www.acmicpc.net/problem/1890

<문제 풀이> 다이나믹 프로그래밍(DP) 알고리즘

dp식을 아래와 같이 정의할 수 있습니다.

dp[i][j] : 가장 왼쪽 위 칸에서 시작해서 (i, j)까지 규칙에 맞게 이동할 수 있는 경로의 개수

(1, 1)은 처음 시작 위치이므로 (1,1)까지 이동할 수 있는 경로의 개수는 1입니다.

-> dp[1][1] = 1

dp[1][1]부터 dp[i][j]까지 dp 값이 잘 계산되었다고 생각하면

(i, j)에서 남쪽방향, 동쪽 방향의 dp값은 다음과 같이 계산할 수 있습니다.

남쪽 방향 = dp[i + arr[i][[j]] += dp[i][j];

동쪽 방향 = dp[i][j + arr[i][j]] += dp[i][j];

(i, j)까지 이동할 수 있는 경로의 개수를 알고 있다고 했을 때 다음 좌표로 점프하는 것은 (i, j)까지의 경로의 개수와 같습니다. 점프는 다른 경로로 생각하는 것이 아니라 같은 경로 이기 때문입니다.

그러나 다음 좌표로 점프하는 (i, j)가 여러 개가 존재하므로 단순히 대입하는 것이 아니라 dp[nx][ny]에 누적해야 합니다.

dp[i][j]값들은 가장 왼쪽 위 칸에서 시작해서 차례로 계산을 하기 때문에 잘 계산되어 있습니다.

한 가지 주의할 점은 경로의 개수는 문제에서 2^63 -1보다 작거나 같다고 했으므로 long long 배열을 선언해야 합니다.

<C++소스코드>

문제 링크: https://www.acmicpc.net/problem/1758

<문제 풀이> 그리디, 정렬 알고리즘

팁 - (받은 등수 - 1)

위 식을 계산했을 때 0보다 작은 경우는 팁을 누적하지 않습니다.

전체 팁의 합을 최댓값으로 만드는 최적의 해는 사람을 배치할 때 팁을 적게 주는 사람을 최대한 뒤로 보내는 것입니다.

예를 들어

50원을 주는 사람이 1등이고, 10원을 주는 사람이 100등이라고 할 때 팁은 다음과 같이 계산됩니다.

50 - (1 - 1) = 50
10 -(100 -1 ) = 0

총 팁 : 50

50원을 주는 사람을 100등, 10원을 주는 사람을 1등이라고 할 때 팁은 다음과 같이 계산됩니다.

50 - (100 - 1) == 0

10 - (1 - 1) = 10

총 팁: 10

위 예시를 보면 뒤에 오는 사람은 식의 값이 0보다 작게 되어서 팁을 누적하지 않습니다.

둘 중에 한 명의 팁을 누적하지 않을 거라면 최대한 팁을 적게 주는 사람을 뒤로 보내 누적하지 않는 것이 최적의 해가 되는 것을 알 수 있습니다.

따라서 팁을 기준으로 내림차순 정렬한 뒤 식의 값을 누적하면 됩니다.

<C++소스코드>

문제 링크: 

<문제 풀이> 그리디 알고리즘

현재까지 발견한 가격들 중 최소의 주유 가격으로 다음 최소 주유 가격을 발견할 때까지 이동하는 것을 반복하면 그것이 최적의 해가 됩니다.

위 그림에서

최솟값 5에서 다음 최솟값을 갱신할 때까지 이동하면 다음 위치는 2

최솟값 2에서 다음 최솟값을 갱신할 때까지 이동하면 다음 위치는 1

구현할 때는 바로 다음 위치까지 이동하는 것이 아닌 도시를 하나씩 방문하면 됩니다.

방문할 때마다 현재까지 발견한 가격들 중 최소의 주유 가격을 임시 변수에 저장하고 있어야 합니다.

현재 도시에서 다음 도시로 이동할 때 드는 비용은 (최솟값*거리)가 됩니다.

<C++소스코드>

문제 링크: https://www.acmicpc.net/problem/11055

<문제 풀이> 다이나믹 프로그래밍(DP) 알고리즘

기본적인 LIS 알고리즘을 구현하면 되는 문제입니다.

dp는 아래와 같이 정의할 수 있습니다.

dp[i] : i 번째까지의 원소를 고려했을 때 가장 큰 증가하는 부분 수열 중에서 합이 가장 큰 것

dp[i]를 갱신하는 방법은 1부터 i -1까지의 dp[j]에 각각에 대해 i 번째 원소를 포함했을 때 그 합이 가장 큰 것으로 갱신해 주면 됩니다.

dp[1] + seq[i] : 1 번째까지의 원소를 고려했을 때 가장 큰 증가하는 부분 수열 중에서 합이 가장 큰 것 + i 번째 원소의 값

dp[2]  + seq[i]: 2 번째까지의 원소를 고려했을 때 가장 큰 증가하는 부분 수열 중에서 합이 가장 큰 것 + i 번째 원소의 값

.

.

dp[j] + seq[i] : j 번째까지의 원소를 고려했을 때 가장 큰 증가하는 부분 수열 중에서 합이 가장 큰 것

.

.

dp[i - 1] + seq[i] : i -1 번째까지의 원소를 고려했을 때 가장 큰 증가하는 부분 수열 중에서 합이 가장 큰 것

	for (int i = 1; i <= n; i++) {
		dp[i] = seq[i]; // 처음에는 자기 자신만 고려
		for (int j = 1; j < i; j++) {
			if (seq[i] <= seq[j]) continue;
			dp[i] = max(dp[i], dp[j] + seq[i]);
		}
	}

<C++소스코드>

문제 링크: https://www.acmicpc.net/problem/14916

<문제 풀이> 그리디 알고리즘

숫자가 큰 동전은 최대한으로 사용하고 숫자가 작은 동전은 최소한으로 사용하는 것이 최적의 해가 됩니다.

N이 5로 나누어 떨어질 때까지 N에서 2를 한 번씩 빼보는 것을 반복하면 됩니다.

N이 5로 나누어 떨어지면 그 몫은 5원 동전의 총 개수

N에서 2를 한 번 빼면 2원 동전 하나 사용

<C++소스코드>