본문 바로가기

코딩일기/알고리즘75

[백준 1149번 : 실버1] RGB거리 (DP/Java) 이번 문제는 내가 어떻게 문제를 풀어야 할지는 감이 약간 잡혔지만 구현 하는 부분에서 애를 먹어 결국 약간의 힌트를 보고 문제를 풀었다. 문제를 살펴보자. 문제 RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자. 1번 집의 색은 2번 집의 색과 같지 않아야 한다. N번 집의 색은 N-1번 집의 색과 같지 않아야 한다. i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다. 입력 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주.. 2021. 7. 28.
[백준 7576번 : 실버1] 토마토 (BFS/Java) 이번 문제는 BFS로 푸는것을 알고 있었고 그에 맞게 알고리즘을 작성하였지만 인접한 정점을 추가하는 단계를 count 하는 부분에서 어떻게 할지몰라 약간의 힌트를 보고 문제를 풀었다. 일단 문제부터 살펴보자. 문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향.. 2021. 7. 28.
[백준 5585번 : 브론즈 2] 거스름돈 (그리디 / Java) 이번 문제는 기본적인 그리디 알고리즘 문제라서 금방 풀수 있었던것 같다. 문제를 살펴보자. 문제 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오. 입력 입력은 한줄로 이루어져있고, 타로가 지불할 돈(1 이상 1000미만의 정수) 1개가 쓰여져있다. 출력 제출할 출력 파일은 1행으로만 되어 있다. 잔돈에 포함된 매수를 출력하시오. 문제 접근 방법 이번 문제는 그리디하게 문제를 풀어야 하기 때문에 제일 먼저해야할것은 가장 큰 액수부터.. 2021. 7. 27.
[백준 11726번 : 실버3] 2xn 타일링 (DP/Java) 이번 문제는 기본적인 DP를 물어보는 문제였다. 사실 처음에 어떻게 풀어야 하나 싶었는데 1부터 한번 방법의 수를 확인해보니 피보나치와 같은 결과가 나온다는걸 알고 금방 풀수 있었다. 그럼 이제 문제를 살펴보자. 문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 문제 접근 방법 일단 이번 문제는 시간제한을 되게 1초 준거보면 일단 시간을 최대한 줄여야 한다. 시간을 줄일수 있는 방법에는 이분탐색, DP가 있는데 나는 이번 알고.. 2021. 7. 27.

티스토리툴바