https://www.acmicpc.net/problem/1592 1592번: 영식이와 친구들 예제 1의 경우 일단 1번이 공을 잡는다. 1번은 공을 한 번 잡았기 때문에, 공을 3번에게 던진다. 3번은 공을 한 번 잡았기 때문에, 공을 5번에게 던진다. 5번은 2번에게 던지고, 2번은 4번에게 던진다 www.acmicpc.net 요즘 문제를 안 풀었더니 하나도 모르겠다.. 이것도 겨우 풀었어.. 안돼~~ 우선, 이 문제는 문제 해결 순서를 올바르게 정하고, 조건에 맞는 회전을 진행해주면 된다. 이것만 해도 충분히 쉽게 구현 가능하다.. #include using namespace std; int n, m, l; int person[52]; void solution(){ int answer = 0; in..

https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 2xn 스티커가 있고, 각 스티커에는 숫자가 적혀있다. 해당 스티커를 떼면 그 숫자를 얻을 수 있다. 숫자의 합이 최대가 되도록 스티커를 떼어내야 한다. 뗄 수 있는 스티커의 점수의 최댓값을 출력해라. 여기서 뗀 스티커의 상하좌우로 붙은 스티커는 뗄 수 없다. 2xn스티커이므로 2xi 스티커라고 가정하고 하나씩 차례대로 최댓값을 구해보자. dp[i][0] = i열의 0행 스티커를 떼어냈..

https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net Nx2 우리가 있고 가로/세로 붙여서 사자를 배치하면 안 된다. 이 우리에 사자를 배치하는 경우의 수를 구하라. N 줄의 우리가 있으니까 i(1~N) 개일 때 경우의 수를 모두 차례대로 구해보면 된다. 1x2 우리에서 사자를 배치하는 경우는 (1,0), (0,1), (0,0) 세 가지 경우가 있다. 이를 토대로, 마지막 줄에 위 세가지 경우를 포함한 경우의 수를 세보면 규칙이 나타난다. i=2일 때는 (1,0)와 (0,1)의 경우는 2가지 (0,0)의 경우는 3가지 i=3일 때는 (1,0)와 (0,1)의 경우는 5가지 (0,0)의..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net N잔의 포도주가 있다. 연속 3잔은 마실 수 없고, 가장 많은 포도주를 마실 수 있도록 해야 한다. 마신 총포도주의 최댓값 출력하라. 이 문제는 BOJ 2579: 계단 오르기 문제와 유사하다! 그러나 여기서는 두 잔을 연속으로 안 마실 수 있다는 점이 다른데, 이 부분이 헷갈렸다.ㅠ0ㅠ 1. dp 이차원 배열을 정하기 dp[i][0] = i-1번째 잔을 마시는 경우 dp [i][1] = i-1번째 ..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net N개의 집이 있고, 1부터 N까지 순서대로 집이 나열되어있다. 모든 집을 RGB 중 하나의 색상으로 칠하는데 드는 최소 비용을 출력하는 문제이다. RGB 색상을 고르는 것에는 규칙이 존재한다. 1번 집의 색은 2번 집의 색과 같지 않아야 한다. N번 집의 색은 N-1번 집의 색과 같지 않아야 한다. i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않..

https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net n개 이전의 값들의 금액 최댓값을 구하다 보면 메모이제이션으로 n개의 카드를 구매하는 금액의 최댓값을 구할 수 있다. #include #include #define num 1002 using namespace std; int n, p[num], dp[num]; void input(){ cin >> n; for(int i=1; i> p[i]; } void solution(){ dp[0] = p[0] = 0..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net n일 동안 일을 하는데, 백준이가 얻을 수 있는 최대 수익은 얼마인지 구하는 프로그램을 작성하면 된다. 완전 탐색과 dp 중 하나를 선택하면 된다. n이 15 이하이므로 완전 탐색도 가능하다. 근데, dp 연습을 하고 싶어서 dp로 해봤다. 규칙 찾는게 생각보다 어려웠다.. 하나의 예시를 잡고 막일(..)을 하면 나름 잘 보이는데 뭔가 너무 꼬아서 생각해서 오히려 독이 되었다. 흑흑 1일부터 n일까지 각 날짜까지만 일을 한다면 구할 수 있는 최대 수익을 구하고 dp배열에 넣고 모두 구하면 max value를 구하면 된다. dp는 이전..

https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 오르막 수 : 수의 자리가 오름차순을 이루는 수 → 인접한 수가 같아도 오름차순으로 친다. 수는 0으로 시작 가능 수의 길이 n이 주어졌을 때, 오르막 수의 개수 구하기(10,007로 나눈 나머지 출력) 길이 1 -> 0, 1, 2, 3,..., 9 = 총 10개 길이 2 -> 00, 01, ... , 11, 12, 13,..., 99 = 총 55개 길이 n -..

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 요약 1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 2. 연속된 세 개의 계단을 모두 밟아서는 안된다. 3. 시작점은 계단에 포함되지 않는다. 4. 마지막 도착 계단은 반드시 밟는다. 1번째 밟고 2번째 혹은 3번째 계단 오를 수 있다. 1번째 밟고 4번째 혹은 2-3번째 계단을 연속으로 모두 밟을 수 없다. 이 게임에서 얻을 수 있는 총점수의 최댓값 구하기 범위 계단의 개수 N (1 ..