본문 바로가기

분류 전체보기411

[C++] 백준 2156번 : 포도주 시식 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 문제 풀이 이전에 계단 오르기와 비슷한 문제. 차이점은 마지막을 포함하는지 안 하는지이다. 따라서 단순하게 3회 연속만 따지면 된다. 첫 잔에서 최대는 당연히 첫 잔이다. 둘째 잔까지도 두 잔의 합이 최대이다. 세 번째부터 약간 달라지는데 연속 3번이 안되기 때문에 최대는 1번 + 2번 or 1번 + 3번 or 2번 + 3번이다. 배열 DP는 n번째 잔까지의 최댓값을 저장하고 glasses는 n번째.. 2021. 6. 18.
[C++] 백준 10844번 : 쉬운 계단 수 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 접근 계단 수는 마지막에 오는 숫자에 따라서 다음에 올 수 있는 숫자가 정해져 있다. 예를 들어서 0 뒤에는 무조건 1, 9 뒤에는 무조건 8이 와야 한다. 그 외에 숫자들은 +1 값과 -1 값이 올 수 있다. (ex. 2 → 1 or 3) 배열 DP는 숫자의 길이와 마지막 수를 인덱스로 가지고 해당 숫자의 길이의 마지막 숫자에 대한 경우의 수를 저장한다. DP [2][3]은 즉, 길이가 2인 숫자의 마지막 숫자가 3의 경우의 수를 저장하고 있다. DP[i][j]를 점화식으로 표현하면 j가 0이면, DP[.. 2021. 6. 18.
[C++] 백준 1463번 : 1로 만들기 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 접근 배열 DP는 연산횟수가 저장된 배열이다. 함수는 3으로 나누었을 때, 2로 나누었을 때, 1을 뺏을 때 세 가지 경우를 따졌을 때 가장 적은 연산횟수를 저장하고 반환한다. 느낀점 처음 작성한 코드가 문제가 있었는데 생각보다 간단하게 이해가 되지 않았었다. 최초의 코드는 모든 경우를 따지지 않고 경우를 나누었기 때문에 최소 연산 횟수를 정확하게 반환하지 못했다. int solution(int n) { if (n == 1 || n == 0) return 0; if (dp[n] == 0) { if (n %.. 2021. 6. 18.
[C++] 백준 2579번 : 계단 오르기 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 풀이 문제에서 마지막 계단은 무조건 밟아야 한다는 조건을 주었다. 그렇다면 주어진 경우는 1. 마지막 계단의 전 계단을 밟는 경우 2. 마지막 계단의 전전 계단을 밟는 경우 dp 배열은 n번째 계단에서 나올 수 있는 최댓값을 저장한다. 그렇다면 점화식은 주어진 경우에 따라 1번 경우 → N번째 계단 + (N-1)번째 계단 + (N-3)번째 계단까지의 최댓값 2번 경우 → N번째 계단 + (N-2)번째 계.. 2021. 6. 3.
[C++] 백준 1932번 : 정수 삼각형 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 문제 풀이 tri 배열에 입력받은 값을 저장한다. 문제에서 입력받은 값들, 즉 원본을 따로 저장하라고 하지 않았기 때문에 바로 배열 값들을 수정하면서 확인하면 된다. 따라서, 2번째 행부터 확인하여 윗 값과 윗 값의 다음 값과 비교해서 더 큰 값을 해당 배열 값에 더하면 된다. 연산이 끝난 이후 마지막 행의 값 중 가장 큰 값을 출력하면 된다. 연산을 할 값의 위치가 가장자리인지 아닌지에 따라 나눌 수 있지만 굳이 그렇게 하지 않아도 연산결과는 같기 때문에 코드를 줄이.. 2021. 6. 2.
[C++] 백준 1149번 : RGB거리 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 풀이 문제의 조건은 앞뒤로 색이 겹치지만 않으면 된다. 따라서, 빨강 → 초록, 파랑 / 초록 → 파랑, 빨강 / 파랑 → 빨강, 초록 이런 식으로 다음에 올 수 있다. prices 배열은 n번의 계산을 저장한 2차원 배열로, 0에는 빨강, 1은 초록, 2는 파랑을 기준으로 잡는다. 각 계산 결과는 조건을 성립하므로 결과 중 제일 작은 값만 출력하면 된다. 느낀 점 처음.. 2021. 6. 1.

티스토리툴바