JAVA - 백준 [BAEK JOON]/동적 계획법 1
[백준] 2579번 : 계단 오르기 - JAVA [자바]
[백준] 2579번 : 계단 오르기 - JAVA [자바]
2020.08.27www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 생각보다 많은 분들이 틀렸던 문제다. 특히 문제 조건을 제대로 이해하지 못하거나 동적계획법을 제대로 이해하지 못해 틀리는 경우가 대다수였던 것 같다. 조건들을 유의하면서 풀어야 하니 차근차근 알아보자. 알고리즘 [접근 방법] 문제는 어렵지 않다. 문제에서 나온 것처럼 크게 다음과 같은 세 가지 조건을 만족해야한다. 1. 계단을 오를 때 한 계단, 또는 두 계단을 오를 수 있다. 2. 연속된 3개의 계단을 밟으면 안된다..
[백준] 1932번 : 정수 삼각형 - JAVA [자바]
[백준] 1932번 : 정수 삼각형 - JAVA [자바]
2020.08.26www.acmicpc.net/problem/1932 1932번: 정수 삼각형 문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최� www.acmicpc.net 문제 조금만 살펴보면 쉽게 풀 수 있는 문제다. 다만 가끔 위에서 아래로 내려오면서 최댓값 경로만 찾아서 하는 경우가 있는데 그렇게 하면 100% 오답이 난다. 또한 DP에 한 번 탐색한 값을 재활용(Memoization)하지 않고 불필요하게 재귀호출을 다 해주면 시간초과가 나니 이 점 유의하도록 하자. 알고리즘 [접근 방법] 정답률이 높은 것을 보아 아마 다들 쉽게 풀 수 있..
[백준] 1149번 : RGB거리 - JAVA[자바]
[백준] 1149번 : RGB거리 - JAVA[자바]
2020.08.11www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 이번 문제는 조금은 생각해 볼 필요가 있는 문제인 것 같다. 대표적으로 풀이방법이 2가지가 있는데, 재귀(Top-Down)방법과 반복문(Bottom-Up)을 이용한 방법. 이렇게 두 가지로 나뉜다. 여타 다른 문제처럼 먼저 재귀를 이용한 풀이를 보여주고, 마지막에 반복문을 사용한 풀이 방법을 알려주겠다. 알고리즘 [접근 방법] 먼저 문제에 대한 이해가 필요하다. 풀이 조건이 조금은 어..
[백준] 9461번 : 파도반 수열 - JAVA [자바]
[백준] 9461번 : 파도반 수열 - JAVA [자바]
2020.08.05www.acmicpc.net/problem/9461 9461번: 파도반 수열 문제 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 � www.acmicpc.net 문제 그동안 배웠던 동적계획법을 응용하여 써보려 한다. 정석적인 방법과 단순 반복문으로 풀이하는 방법 모두 보여줄 것이다. 알고리즘 [접근 방법] 그동안의 동적계획법 문제는 테스트 케이스가 1개뿐으로 해당 값에 대한 재귀 또는 반복문으로 풀었었다. 이번 문제는 테스트 케이스가 여러개이므로 각 케이스마다 동적계획법을 쓰려 한다. 예로들어 Func() 함수가 있다고 가정하자. 이 함수는 Fucn(N) = Func(N..
[백준] 1904번 : 01타일 - JAVA [자바]
[백준] 1904번 : 01타일 - JAVA [자바]
2020.07.24www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이�� www.acmicpc.net 문제 문제의 이해 자체는 어렵지 않을 것이다. 타일은 두 종류가 있는데 1타일과 0이 두 개 이어 붙여진 00타일이 있는 것이다. 즉 1타일과 00타일을 조합할 때, 00타일은 분해할 수 없다는 의미다. 막상 풀어보면 그렇게 어렵지 않으니 한 번 같이 문제를 들여다보도록 하자 알고리즘 [접근 방법] 이 문제는 만약 N=1 부터 경우의 수를 쭉 나열해보았다면 매우 쉽게 풀 수 있다. 일단 한 번 나열해보도록하자. ..