본문 바로가기

알고리즘/백준118

백준 2156 포도주 시식 (JAVA 자바 풀이) 백준 2156 포도주 시식 (JAVA 자바 풀이) 📌 문제 예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다. ⚔ 입력 첫째 줄에 포도주 잔의 개수 n이 주어진다. (1 ≤ n ≤ 10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다. 📣 출력 첫째 줄에 최대로 마실 수 있는 포도주의 양을 출력한다. 💎 문제 분석 처음 풀이에서는 그림과 같이 dp[2]일때만 고려하여 직전과 직전의 직전 dp만을 계산했다. 하지만 선택을 안하.. 2022. 12. 13.
백준 10844 쉬운 계단 수 (JAVA 자바 풀이) 백준 10844 쉬운 계단 수 (JAVA 자바 풀이) 📌 문제 45656이란 수를 보자. 이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다. ⚔ 입력 첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 📣 출력 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. 💎 문제 분석 점화식 자체는 단순할 수 있지만 케이스를 0일 때와 9일때로 나눠주는 부분에서 생각이 필요하다. 또한 자바의 경우 자료형을 신경써주어야 해서 이런 문제는 차라리 파이썬으로 푸는게 속편할 수 있다. 💡 코드 구현 import java.io.Buff.. 2022. 12. 12.
백준 2579 계단 오르기 (JAVA 자바 풀이) 백준 2579 계단 오르기 (JAVA 자바 풀이) 📌 문제 각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오. ⚔ 입력 입력의 첫째 줄에 계단의 개수가 주어진다. 둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다. 📣 출력 첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다. 💎 문제 분석 점화식은 생각보다 간단한데 100%에서 계속 런타임 오류가 났다. 입력 범위가 작은 경우 배열 초기화를 N+1로 할 경우 처리를 못하는 에러가 발생한다(e.g. 1 -> 2,3에 대한 에.. 2022. 12. 11.
백준 1932 정수 삼각형 (JAVA 자바 풀이) 백준 1932 정수 삼각형 (JAVA 자바 풀이) 📌 문제 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다. ⚔ 입력 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. 📣 출력 첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다. 💎.. 2022. 12. 10.
백준 1149 RGB 거리 (JAVA 자바 풀이) 백준 1149 RGB 거리 (JAVA 자바 풀이) 📌 문제 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자. ⚔ 입력 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다. 📣 출력 첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다. 💎 문제 분석 N의 최대값이 10,000,000에 시간제한은 1초이므로 반복문을 사용하면 100% 시간 초과가 날 것이고 일일히 구하는 것이 아니라 숫자를 .. 2022. 12. 9.

티스토리툴바