티끌모아 태산

https://www.acmicpc.net/problem/9657 9657번: 돌 게임 3 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 설명 핵심 아이디어 기존의 돌 게임 문제와 유사하다. 차이점이 있다면 가져갈 수 있는 돌의 개수가 1개, 3개에서 추가로 4개단위도 가져갈 수 있게 됐다. 다이나믹 프로그래밍: 작은 문제부터 풀어보자 dp[1] ~ dp[4] 에 대해서 배열에 저장해 놓고 푼다. 상근이부터 시작할 때 돌이 1개, 3개, 4개 있을 때는 무조건 상근이가 승리한다. 하지만 돌이 2개 있을 때는 상근이가 1개 밖에 가져갈 수 없기 때문에 창영이가 승리한다. 돌이 5개 이상일 때는 한번에 게임이 끝나지 않기 때문에 상근이가 1개 3개 4개..

https://www.acmicpc.net/problem/9655 9655번: 돌 게임 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 설명 핵심 아이디어 다이나믹 프로그래밍 작은 문제부터 시작하자! 돌의 개수가 홀수 일 때는 SK이고 돌의 개수가 짝수 일 때는 CY를 출력하면 된다. 코드 구현 # 1 처음에는 풀었을 때 답은 맞았으나 시간이 오래 걸려서 갸우뚱 했었다. DP로 푸는게 맞나 싶은 생각이 들었다. import sys input = sys.stdin.readline n = int(input()) dp = [""] * (n+1) for i in range(1, n+1): if i % 2 == 0: dp[i] = "CY" else: dp[i]..

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 설명 맨 위층에서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램 작성. 핵심 아이디어 다이나믹 프로그램이 작은 문제부터 먼저 풀자! 맨 왼쪽 계산과 맨 오른쪽 계산 그리고 중간을 max() 활용해서 비교해주면 된다! 맨 왼쪽인 경우(j=0): dp[i][j] += dp[i-1][j] 맨 오른쪽 인 경우(j=맨끝): dp[i][j] += dp[i-1][j-1] 가운데 경우는 max()활용: dp[..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 설명 상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램 계산하자. 오늘부터 N+1 일째 되는 날 퇴사하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다. 따라서 하루에 하나씩 서로 다른 사람의 상담을 잡아 놓았다. 각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어 져 있다. 핵심 아이디어 다이나믹 프로그래밍은 큰 문제를 작은 부분으로 나누고, 그 작은 부분 문제들이 반복되는 것을 이용하여 풀어 가는 방법이다. 모든 작은 문제들을 단 한번만 풀어야..

https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 설명 카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최댓값을 구하는 프로그램 작성. 이때, N개보다 많은 개수의 카드를 산 다음, 나머지 카드를 버려서 N개를 만드는 것을 불가능. 즉, 구매한 카드팩에 포함되어 있는 카드 개수의 합은 N과 같아야 한다. 카드는 카드팩의 형태로만 구매 가능. 각 카드에는 등급이 있고 8가지 등급으로 나뉘어짐. 카드팩의 종류는 카드..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 설명 테이블 위에 다양한 포주가 들어있는 포도주 잔이 일렬로 놓여있다. 이를 시식하기 위해서 다음 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 있는 포도주는 모두 마셔야하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 최대한 많은 양의 포도주를 맛보기 원한다. 따라서 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램 작성. 예를들어,..

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 설명 n개의 정수로 이루어진 수열에서 연속된 몇 개의 수를 선택해 가장 큰 합을 출력하는 프로그램 작성. 예를들어, 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌을 때, 정답은 12 + 21 인 33이다. 핵심 아이디어 최대 계산 값을 계속 기록하면서, 최대한 빠른 시간 안에 해결하는 것이다. Memorization(기억법)을 활용하는 것으로 대표적이로 DP 스킬 중 ..

https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 설명 N(1

https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 설명 문제는 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. 1 n >> m; // 배열 입력 받기 for (int i = 1; i > arr[i]; } // 배열을 누적합으로 변경 for (int i = 1; i > a >> b; cout

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 설명 우선, 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 계단을 밟으면 각 계단에 쓰여있는 점수를 얻게 된다. 예를들어, 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75 점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 또는 두 계단식 오를 수 있다. 즉 한 번..