[백준] 3085번 사탕게임 - Java 문제 출처 https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다. www.acmicpc.net ※ 풀이 사탕의 위치를 한번 바꿔서 만들수 있는 가장 긴 사탕 열을 찾는 문제이다. 문제에서 준 범위가 크지 않으므로 브루트포스로 모든 경우의 수를 해보면서 체크하면 된다. ※ 소스코드 import java.io.*; import java.util.*; import java.util.stream.*; public class Main { public static void main(String[] args) throws IOException { //input BufferedRe..
알고리즘/백준
[백준] 2309번 일곱난장이 - Java 문제 출처 https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net ※ 풀이 전형적으로 브루트포스로 가능한 경우의 수를 다 해보면 되는 문제이다. 가능한 경우의 수를 계산을 해보았을 때 9명의 난쟁이 후보들이 있고 각각 난쟁이일 경우, 아닐경우 경우의 수가 있으니 2^9 정도라고 예상을 해볼 수 있다. 이는 제한시간이 2초임을 감안했을 때 충분히 풀 수 있는 시간이다. (1초에 약 1억번의 연산이 가능하다고 생각하면 된..
[백준] 11727번 2×n 타일링 2 - Java 문제 출처 www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net ※ 풀이 동적프로그래밍(DP)을 활용하여 푸는 대표적인 유형이다. 이 문제도 2xn 문제 1번 과 유사하지만 2x2 블럭이 추가되었다. 마찬가지로 n번째 점화식을 세우기 위해 블럭의 수를 추론해보면 a[1]=1 a[2]=3 ... a[n] = a[n-1] + 2* a[n-2] 형태로 n-2 일때 * 2를 해야 하는 식이 나온다. (n-2일때 블럭이 n-1일때 들어가지 못하는 형태..
[백준] 11726번 2×n 타일링 - Java 문제 출처 www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net ※ 풀이 동적프로그래밍(DP)의 대표유형격인 문제이다. n 번째 경우의 점화식을 세워서 값을 저장해나가면서 풀어가면 되는데 이 경우 단순하게 a[1]=1 a[2]=2 ... a[n]=a[n-1]+a[n-2] 방식으로 점화식을 세워서 재귀호출을 이용하여 풀어보았다. ※ 소스코드 import java.io.BufferedReader; import java.io.IOExcepti..
