기록방

👉 문제링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🔸 문제 분석 🔸 0에서 n까지 이동하는 최소 점프 수를 반환한다. 점프하면 한 칸 앞으로 이동한다. 텔레포트하면 현재 인덱스의 2배 인덱스로 이동하고, 점프 수는 증가하지 않는다. 🔸 문제 풀이 🔸 텔레포트는 짝수 인덱스에서만 가능하고, 점프 수가 증가하지 않으므로 무조건 많이 쓰면 좋다. 0부터 시작해 n으로 향하면, 쓸 데 없는 경우의 수가 많아지므로 확실히 도착하는 경로를 찾기 위해서 n부터 시작해 0으로 끝나도록 계산한다. 현재 수가 짝수라면 n/2 절반 인덱스로 이동한다. (텔레포트) ..

👉 문제링크 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 🔸 문제 분석 🔸 N * 3 보드판을 내려가며 최대,최소값을 구하는 문제이다. 내려갈 수 있는 방법이 3가지가 있는데, 브루트포스로 그래프 탐색하면 시간초과가 난다. 내려가는 방법이 아닌, 역으로 이전 줄을 보고 최대/최소값을 고르는 DP 방식으로 풀이할 수 있다. 🔸 코드 🔸 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io...

👉 문제링크 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 🔸 문제 분석 🔸 N개의 집에 R,G,B 3가지 색이 연속하지 않도록 칠한다. 각 집의 세 가지 색에 대한 비용이 주어진다. 모든 집을 칠하는 최소비용을 출력한다. 칠하는 경우의 수를 구하면 3x2x2x...x2 = 3x2x(n-1) = 6(n-1) n은 최대 1,000이므로, 칠하는 경우의 수는 최대 5994가지 가지수가 많지 않아 재귀, 백트래킹을 사용한 브루트 포스도 가능할 것 같지만, 시간은 0.5초이므로 DB를 이용한다..

👉 문제링크 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 🔸 문제 분석 🔸 n가지 동전으로 k원을 만드는 경우의 수를 출력한다. 동전을 무한으로 쓸 수 있으면 전형적인 DP문제로, dp[i] 는 i원을 만들 수 있는 경우의 수이다. 🔸 코드 🔸 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { pu..

👉 문제링크 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 🔸 문제 분석 🔸 N x N 격자공간에서 좌상단부터 우상단으로 파이프를 이동시킬 수 있는 경우의 수를 출력한다. 파이프는 오른쪽, 우하단 대각선, 아래로 밀 수 있다. 격자공간에는 돌이 있다. 파이프를 돌릴 때 확보되어야 하는 공간에 돌이 있거나 격자 공간을 벗어나서는 안된다. DFS로 끝까지 도착하는 경우를 카운트한다. 기존 가로 일때는 가로와 대각선, 기존 세로 일때는 세로와 대각선, 기존 대각선 일때는 세 가지 모든 경우..