본문 바로가기

dp57

[백준 31910] 이진수 격자 (C++) https://www.acmicpc.net/problem/31910문제각 칸에 0 또는 1이 적혀 있는 N×N격자가 있다. 인선이는 1행 1열에서 출발해 N행 N열까지 이동하는데, 오른쪽(열 번호가 증가하는 방향) 또는 아래(행 번호가 증가하는 방향)로만 한 칸씩 이동할 수 있다. 인선이는 어떤 칸에 방문할 때마다 그 칸에 적힌 문자를 자신이 갖고 있는 문자열의 뒷부분에 덧붙인다. 예를 들어, 주어진 그림에서 인선이가 1행 1열에서 출발하여 순서대로 오른쪽, 아래, 오른쪽으로 한 칸씩 이동한다면 인선이가 가진 문자열은 1101이다.N행 N열에 도착하면 인선이는 자신이 갖고 있는 문자열을 이진수로 해석한 값 M을 계산한다. 예를 들어, 인선이가 가진 문자열이 1101일 경우 M=13이다. 인선이가 계산하게.. 2025. 1. 25.
[백준 20500] Ezreal 여눈부터 가네 ㅈㅈ (C++) 문제욱제는 15라는 수를 굉장히 싫어한다. 그래서 0으로 시작하지 않고 1과 5로만 구성된 N자리 양의 정수 중에서, 15의 배수가 몇 개인지 궁금해졌다.참가자 여러분도 궁금하지요?안 궁금함? 15ㄱ 입력 N이 주어진다. 출력문제의 답을 1 000 000 007로 나눈 나머지를 출력한다.제한 1 ≤ N ≤ 1515 문제 풀이 dp 문제. 15로 나누어 떨어지려면 5로 나누어 떨어져야 하고, 3으로도 나누어 떨어져야 한다. 따라서 맨 마지막 자릿수는 5 고정이고, 모든 자릿수의 합이 3의 배수여야 한다.dp를 이용하여 i자리 자릿수 중 3으로 나누었을 때 나머지가 0, 나머지가 1, 나머지가 2인 수의 개수를 구한다. i-1자리 자릿수에 1 또는 5를 붙여 i자리 자릿수를 만든다. 1은 나머지가 1추가 되.. 2025. 1. 20.
[백준 1106] 호텔 (C++) https://www.acmicpc.net/problem/1106문제세계적인 호텔인 형택 호텔의 사장인 김형택은 이번에 수입을 조금 늘리기 위해서 홍보를 하려고 한다.형택이가 홍보를 할 수 있는 도시가 주어지고, 각 도시별로 홍보하는데 드는 비용과, 그 때 몇 명의 호텔 고객이 늘어나는지에 대한 정보가 있다.예를 들어, “어떤 도시에서 9원을 들여서 홍보하면 3명의 고객이 늘어난다.”와 같은 정보이다. 이때, 이러한 정보에 나타난 돈에 정수배 만큼을 투자할 수 있다. 즉, 9원을 들여서 3명의 고객, 18원을 들여서 6명의 고객, 27원을 들여서 9명의 고객을 늘어나게 할 수 있지만, 3원을 들여서 홍보해서 1명의 고객, 12원을 들여서 4명의 고객을 늘어나게 할 수는 없다.각 도시에는 무한 명의 잠재적.. 2025. 1. 17.
[백준 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.

티스토리툴바