https://www.acmicpc.net/problem/2846 백준 2846번 오르막길 문제를 풀어보았다.해당 문제를 어떻게 풀어야할까!!!!! 일단 입력 값을 배열에 넣고 앞의 값과 뒤의 값을 비교하면서 뒤에 있는 값이 더 크면 오르막길 차이를 sum에 더해주고아닌 경우에는 max 값과 비교하여 max를 할당하고 sum을 초기화 해주면 되겠다는 방법을 생각했다. 생각한 것을 코드로 구현한 것이 아래와 같다.문제 푼 코드1import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { public stati..

https://www.acmicpc.net/problem/2476 백준 2476번 주사위 게임 문제를 풀어보았다. 문제를 처음 풀었을 때 이중 배열을 만들어서 주사위 눈의 빈도를 카운팅하도록 구현하고금액을 계산하는 부분은 함수로 분리하여 처리를 하였다. 문제 푼 코드1import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedRea..

https://www.acmicpc.net/problem/9095 백준 9095번 1, 2, 3 더하기 문제를 풀어보았다.해당 문제는 n이 주어지면 1, 2, 3으로만 더해서 합이 n이 되는 모든 방법의 수를 구하는 문제이다. n을 만들 수 있는 방법은 아래와 같다.n-1을 만드는 모든 방법에 +1을 붙이는 법n-2를 만드는 모든 방법에 +2를 붙이는 법n-3를 만드는 모든 방법에 +3을 붙이는 법해당 방법을 점화식으로 표현하면 아래와 같다.dp[n] = dp[n-1] + dp[n-2] + dp[n-3]마지막에 1을 붙였다면 앞에 n-1을 만들어야한다. -> dp[n-1]마지막에 2를 붙였다면 앞에 n-2를 만들어야한다. -> dp[n-2]마지막에 3을 붙였다면 앞에 n-3을 만들어야한다. -> dp[n..

https://www.acmicpc.net/problem/9375 백준 9375번 패션왕 신혜빈 문제를 풀어보았다.해당 문제는 새로운 조합의 문제였다! 일단 무조건 의상 개수는 결과값에 포함이 되어야 하고 그 다음은 종류별로 겹치지 않게 조합을 구해야 하는데이건 단순 조합으로 푸는게 아니라 경우의 수를 구해야 한다. 개인적으로 핵심 요점이라고 생각하는 부분은아무 옷도 입지 않는 경우는 오직 한 가지 경우만 존재한다. 이부분이였다. 예시로hat - headgearturban - headgearsunglasses - eyewear 위와 같이 있으면headgear는 hat, turban, 안입음 총 3가지가 있고(선택지 3개)eyewear는 sunglasses, 안입음 총 2가지가 있다.(선택지 2개)전체 가..

https://www.acmicpc.net/problem/1149 동적 계획법(다이나믹 프로그래밍)의 감을 잡아가는 중이라 백준 1149번 RGB거리 문제를 풀어보았다. 해당 문제는 i번째 집 색상과 i-1, i+1번째 집 색상은 같을 수 없다는 규칙을 지키면서 색상을 칠하는 최소 비용을 구해야 하는 문제이다. 첫번째 집(dp[0][0], dp[0][1], dp[0][2])은 각각 입력으로 주어진 R, G, B 색상에 대한 비용으로 초기화를 해주고이후 반복문을 통해서현재 집을 R로 칠했을 때 이전의 집의 G, B 비용 중 더 저렴한 비용을 현재 집 R 비용을 더한 것을 dp 배열에 저장현재 집을 G로 칠했을 때 이전의 집의 R, B 비용 중 더 저렴한 비용을 현재 집 G 비용을 더한 것을 dp 배열에 저..

https://www.acmicpc.net/problem/2579 백준 2579번 계단 오르기 문제를 풀어 보았다. 규칙을 지키면서 계단을 오를 때 누적 합이 최고 값을 출력하는 문제이다. 계단을 오를 때의 규칙은 다음과 같다.계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. (한 계단을 밟으면 다음 계단 또는 다음 다음 계단으로 오를 수 있음)연속된 세 개의 계단을 밟아서는 안된다.(시작점은 계단에 포함되지 않음)마지막 도착 계단은 반드시 밟아야 한다.처음에는 마지막 도착 계단을 반드시 밟아야 한다는 문구를 보고 오르는게 아니라 내리는 것처럼 구현하려고 했는데이렇게 구현하면 동적 계획법으로 구현하는 게 아니라고 하여 동적 계획법을 사용해서 구현할 수 있도록 문제를 풀었다. 동적 계획법은 경로를..