Algorithm

[백준 2217번] 로프 (C++)

https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 로프 문제는 그리디 알고리즘을 이용하여 해결할 수 있습니다. 먼저, 버틸 수 있는 최대 중량이 가장 높은 로프부터 골라야 높은 중량의 물체를 들 수 있습니다. 따라서, 최대 중량을 기준으로 정렬을 수행해야합니다. n번째부터 i번째까지 로프를 선택했을 때, 들 수 있는 최대 중량은 Si * (n - i)입니다. (단, Si는 i번째 로프의 최대 중량) 왜냐하면 i번째 로프의 최대 중량이 가..

[백준 4883번] 삼각 그래프 (C++)

https://www.acmicpc.net/problem/4883 4883번: 삼각 그래프 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 그래프의 행의 개수 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N개 줄에는 그래프의 i번째 행에 있는 정점의 비용이 www.acmicpc.net 삼각 그래프 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다. ⚠️ 단, 비용이 음수가 될 수 있다는 것을 주의해야합니다. 먼저, 테이블 d[i][j]는 i행 j열로 이동하는 최소 비용으로 정의했습니다. 따라서, 초기값은 아래와 같습니다. d[0][0] = INT_MAX, d[0][1] = graph[0][1], d[0][2] = graph[0][1] + graph[0][..

[백준 11057번] 오르막 수 (C++)

https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 오르막 수는 N이 1,000이므로, 모든 경우의 수를 구하는 경우 시간 초과가 발생합니다. 오르막 수는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다. 먼저, 테이블 d[i][j]는 길이가 N이고, i로 끝나는 오르막 수의 개수로 정의했습니다. 초기값 d[0][1] ~ d[9][1]은 모두 1입니다. 또한, d[i][j]는 길이가 N - 1이고, j보다 작거..

[백준 9465번] 스티커 (C++)

https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 스티커 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다. 테이블 d[i][j]는 d[0]부터 d[i]까지의 스티커를 선택했을 때, 스티커 점수의 최댓값으로 정의했습니다. (단, d[i][j] 스티커는 반드시 선택) 초기값은 아래와 같습니다. // 단, board는 2행 n열의 스티커 배열을 의미함 d[0][0] = board[0][0]; d[1][0] = board[1][0];..

[백준 11052번] 카드 구매하기 (C++)

https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 카드 구매하기는 n이 최대 1,000이므로 백트래킹을 이용하면 시간 초과가 발생할 수 있습니다. 카드 구매하기는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다. 다이나믹 프로그래밍의 테이블 d[i]는 카드 i개를 구매하기 위해 지불해야하는 금액의 최댓값으로 정의했습니다. d[1]은 경우의 수가 하나이므로, d[1] = p[1]입니다. 돈을 최대한 많이 지불하여 n개의 카드를 구매하려면, 가성비가 가장..

[백준 2302번] 극장 좌석 (C++)

https://www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net 극장 좌석 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다. N이 최대 40이므로, 경우의 수가 40!입니다. 따라서 백트래킹을 이용하면 시간 초과가 발생할 수 있습니다. vip 좌석의 경우 고정석입니다. 따라서 vip 석을 제외하고, 경우의 수를 계산해야합니다. 아래의 경우, 가능한 좌석 배치는 1개입니다. 1 vip 아래의 경우 가능한 좌석 배치는 2개입니다. 1 2 vip 1 2 vip 2 1 ..

[백준 15988번] 1, 2, 3 더하기 3 (C++)

https://www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 1, 2, 3 더하기 3 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다. 1을 만드는 경우의 수는 아래와 같습니다. 1 2를 만드는 경우의 수는 아래와 같습니다. 1 + 1 2 3를 만드는 경우의 수는 아래와 같습니다. 1 + 1 + 1 + 1 1 + 1 + 2 1 + 2 + 1 1 + 3 4를 만드는 경우의 수는 아래와 같습니다. 3 + 1 2 + 1 + 1 2 + 2 1 + 1 + 1 + 1 1 + 1 + 2 1 + 2 + 1 1 +..

[백준 2156번] 포도주 시식 (C++)

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 포도주 시식 문제는 N이 최대 10,000이므로 모든 경우의 수를 계산하는 경우 시간 초과가 발생할 수 있습니다. 포도주 시식 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다. 테이블 d[i]는 i번째 포도주까지 시식했을 때의 최대 포도주의 양으로 정의했습니다. 초기 값 d[1] = 첫번째 포도주의 양, d[2] = 첫번째 포도주의 양 + 두번째 포도주의 양입니다. 연속으로 놓여있는 3잔을..