본문 바로가기

Wook's 개척일기234

[백준 9095번 : 실버3] 1,2,3 더하기 (DP / Java) 이번 문제는 DP라고 해서 1부터 값을 저장하는건가? 까지 생각을 했지만 그 생각이 답까지 이어지진 못했다. 그래서 결국 답을 확인해봤다. 문제부터 살펴보자. 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. 문제 접근 방법.. 2021. 7. 24.
[백준 2178번 : 실버 1] 미로탐색 ( BFS/ Java) 이번 문제는 BFS로 내가 잘 풀려고 했고 내가 생각한 알고리즘은 맞았지만 인접 노드 구하는 부분에서 애를 먹어서 풀지 못하고 결국엔 답을 찾아 봤다. 일단 문제부터 보자. 문제 N×M크기의 배열로 표현되는 미로가 있다. 1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 1 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다. 위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도.. 2021. 7. 23.
[백준 : 실버2] 동전 0 : 그리디 알고리즘(Java) 이번 문제는 생각외로 정말 쉬웠다. 문제부터 살펴보자. 문제 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) 출력 첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다. 문제 접근 나는 이번문제를 어떻게 접근 했냐면 일단 가장 적은 동전의 수를 사용하려면 일단 수가 가장큰거부터 .. 2021. 7. 22.
[백준 : 실버3] 1로 만들기(1463 번) : DP(Java) 이번 문제는 동적프로그래밍으로 어떻게 풀어보려고 했으나 아직 익숙치 않은지 감이 잡히질 않았다. 그래서 답을 보게 되었는데 이제 약간 동적프로그래밍이 뭔지 알것 같다. 문제부터 살펴보자. 문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 힌트 10의 경우에 10 -> 9 -> 3 -> 1 로 3번 만에 만들 수 있다. 문.. 2021. 7. 22.

티스토리툴바