본문 바로가기

dp54

[백준 2624] 동전 바꿔주기 (C++) https://www.acmicpc.net/problem/2624문제명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 n1, n2, … , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고 한다. 이때, 동전 교환 방법은 여러 가지가 있을 수 있다. 예를 들어, 10원 짜리, 5원 짜리, 1원 짜리 동전이 각각 2개, 3개, 5개씩 있을 때, 20원 짜리 지폐를 다음과 같은 4가지 방법으로 교환할 수 있다.20 = 10×2 20 = 10×1 + 5×2 20 = 10×1 + 5×1 + 1×5 20 = 5×3 + 1×5입력으로 지폐의 금액 T, 동전의 가지 수 k, 각 동전 하나의 금액 pi와 개수 ni가 주어질 때 (i=1, 2,…, k) 지폐를 동전으로 교환하는 방법의.. 2025. 1. 4.
[백준 28706] 럭키 세븐 (C++) https://www.acmicpc.net/problem/28706문제당신은 양의 정수 K를 하나 가지고 있습니다. 처음에 K=1입니다.당신에게는 N개의 턴이 주어지고, 각 턴에는 2개의 선택지 중 하나를 골라야합니다. 각각의 선택지는 “+ v” 혹은 “* v”와 같은 방식으로 주어집니다. (1 ≤ v ≤ 9)“+ v ”: K를 K+v로 바꿉니다.“* v ”: K를 K×v로 바꿉니다.선택지를 모두 고른 이후 결과로 나온 K가 7의 배수가 되도록 할 수 있나요?입력첫 줄에 테스트케이스의 수 T가 주어집니다. (1 ≤ T ≤ 10000)각 테스트케이스의 첫 줄에 턴의 수 N이 주어집니다. (1 ≤ N ≤ 200000)다음 N개의 줄의 i번째 줄은 “ op1 v1 op2 v2 ”와 같은 방식으로 모든 문자를 .. 2024. 12. 28.
[백준 16194] 카드 구매하기 2 (C++) https://www.acmicpc.net/problem/16194문제요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다.PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다.전설카드레드카드오렌지카드퍼플카드블루카드청록카드그린카드그레이카드카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재한다.민규는 지난주에 너무 많은 돈을 써 버렸다. 그래서 오늘은 돈을 최소로 지불해서 카드 N개를 구매하려고 한다. 카드가 i개 포함된 카드팩의 가격.. 2024. 12. 26.
[백준 28422] XOR 카드 게임 (C++) https://www.acmicpc.net/problem/28422문제XOR 카드 게임이란 N장의 카드 더미가 있을 때, 맨 위에서부터 카드를 두 장 혹은 세 장씩 가져가 점수를 획득하는 게임이다. 이 게임에서 점수는 아래 단계를 거쳐 누적해서 획득할 수 있다.한 번에 가져가는 카드들에 적혀있는 번호를 XOR 연산한다.1에서 구한 값을 이진수로 변환했을 때, 1의 개수만큼 점수를 획득한다.게임을 진행하며 주의할 점은 마지막에 카드 한 장이 남는 상황이 존재할 수 있는데, 이 경우엔 모든 점수를 잃고 0점으로 게임을 종료하게 된다. 이 게임에서 얻을 수 있는 최고 점수를 계산하시오. 입력첫째 줄에 카드 더미에 있는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 100000)둘째 줄에 각 카드에 적힌 정수 A.. 2024. 12. 8.
[백준 10164] 격자상의 경로 (C++) https://www.acmicpc.net/problem/10164문제행의 수가 N이고 열의 수가 M인 격자의 각 칸에 1부터 N×M까지의 번호가 첫 행부터 시작하여 차례로 부여되어 있다. 격자의 어떤 칸은 ○ 표시가 되어 있다. (단, 1번 칸과 N × M번 칸은 ○ 표시가 되어 있지 않다. 또한, ○ 표시가 되어 있는 칸은 최대 한 개이다. 즉, ○ 표시가 된 칸이 없을 수도 있다.) 행의 수가 3이고 열의 수가 5인 격자에서 각 칸에 번호가 1부터 차례대로 부여된 예가 아래에 있다. 이 격자에서는 8번 칸에 ○ 표시가 되어 있다.격자의 1번 칸에서 출발한 어떤 로봇이 아래의 두 조건을 만족하면서 N×M번 칸으로 가고자 한다. 조건 1: 로봇은 한 번에 오른쪽에 인접한 칸 또는 아래에 인접한 칸으로만.. 2024. 12. 4.
[백준 17485] 진우의 달 여행 (Large) (C++) https://www.acmicpc.net/problem/17485문제우주비행이 꿈이였던 진우는 음식점 '매일매일싱싱'에서 열심히 일한 결과 달 여행에 필요한 자금을 모두 마련하였다! 지구와 우주사이는 N X M 행렬로 나타낼 수 있으며 각 원소의 값은 우주선이 그 공간을 지날 때 소모되는 연료의 양이다. 진우는 여행경비를 아끼기 위해 조금 특이한 우주선을 선택하였다. 진우가 선택한 우주선의 특징은 아래와 같다. 1. 지구 -> 달로 가는 경우 우주선이 움직일 수 있는 방향은 아래와 같다.2. 우주선은 전에 움직인 방향으로 움직일 수 없다. 즉, 같은 방향으로 두번 연속으로 움직일 수 없다.진우의 목표는 연료를 최대한 아끼며 지구의 어느위치에서든 출발하여 달의 어느위치든 착륙하는 것이다.최대한 돈을 아끼.. 2024. 12. 2.
[백준 16568] 엔비스카의 영혼 (C++) https://www.acmicpc.net/problem/16568문제한길이는 수습 마법사이며, 마법사의 영혼을 받기 위해 줄을 서있다. 한길이는 강력한 힘을 얻기 위해 인성을 버렸다. 그리고 최고로 강력한 엔비스카의 영혼을 받기 위해서 새치기를 하기로 결심했다.한길이의 앞에 N명의 사람들이 줄 서있다. 1초가 지날 때마다 줄의 맨 앞 사람은 영혼을 받고 집에 간다. 그리고 1초마다 한길이는 다음과 같은 행동을 할 수 있다.기다리기a명 앞으로 가기 (앞에 최소 a명 있을 때)b명 앞으로 가기 (앞에 최소 b명 있을 때)단, 한길이는 새치기에는 도가 텄기때문에, 모든 행동을 0초만에 할 수 있다.예를 들어 N = 5, a = 1, b = 2라고 하자. 5초동안 기다리기만 하면 줄의 맨 앞 사람이 나가기 때.. 2024. 12. 1.
[백준 16500] 문자열 판별 (C++) https://www.acmicpc.net/problem/16500문제알파벳 소문자로 이루어진 문자열 S와 단어 목록 A가 주어졌을 때, S를 A에 포함된 문자열을 한 개 이상 공백없이 붙여서 만들 수 있는지 없는지 구하는 프로그램을 작성하시오. A에 포함된 단어를 여러 번 사용할 수 있다.입력첫째 줄에 길이가 100이하인 문자열 S가 주어진다. 둘째 줄에는 A에 포함된 문자열의 개수 N(1 ≤ N ≤ 100)이 주어진다. 셋째 줄부터 N개의 줄에는 A에 포함된 단어가 한 줄에 하나씩 주어진다. A에 포함된 문자열은 알파벳 소문자로만 이루어져 있고, 길이는 100을 넘지 않는다. 출력A에 포함된 문자열로 S를 만들 수 있으면 1, 없으면 0을 출력한다. 문제 풀이dp 문제. dp[i]가 dp[i-1]번째.. 2024. 11. 23.
[백준 11051] 이항 계수 2 (C++) https://www.acmicpc.net/problem/11051문제자연수 N과 정수 K가 주어졌을 때 이항 계수 (NK)를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오. 입력첫째 줄에 N과 K\가 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ K ≤ N) 출력 (NK)를 10,007로 나눈 나머지를 출력한다. 문제 풀이다이나믹 프로그래밍 문제. NCK = N-1CK-1 + N-1CK임을 이용해 2차원 dp 배열을 채워주면 된다. 따라서 dp[i][j] = dp[i-1][j-1] + dp[i-1][j]가 성립한다.NC0와 NCN은 각각 N개 중 아무것도 뽑지 않는 경우와 N개 중 N개를 모두 다 뽑는 경우이므로 둘 다 1이다. 따라서 dp[i][0]= dp[i][i] = 1이다. 아래는 코.. 2024. 11. 8.

티스토리툴바