2025/08 6

[JAVA] BOJ 14501 퇴사 DP

문제 설명일할 수 있는 요일을 지정해서 최대 요금을 구해야 하는문제여러 방법을 생각했는데, 가장 효율적인 방법은 아니게 풀었다.방법 1. 이중 for문방법 2. 완전 DP풀이내 풀이해당 날짜가 되면 그 날짜에 도달할 수 있는 경우의 수가 있는지 for문으로 탐색한다. 시간복잡도가 그렇게 크지 않아서 가능했던 풀이 방식이다.import java.util.*;import java.io.*;class Main { static int N; static int[][] arr; static int[] dp; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader..

[JAVA] BOJ 3190 뱀

문제문제 설명'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.만약 벽이나 자기자신의 몸과 부딪히면 게임이 끝난다.만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가..

[프로그래머스] 단어 변환

문제문제 설명두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.한 번에 한 개의 알파벳만 바꿀 수 있습니다.words에 있는 단어로만 변환할 수 있습니다.예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는..

[Java] BOJ 1912 연속합

문제문제 내용n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.입력첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.출력첫째 줄에 답을 출력한다.예제 입력 11010 -4 3 1 5 6 -35 12 21 -1예제 출력 133풀이아이디어경우의 수를 두 가지로 나누어 생각할 수 있다.arr[..

[Java] BOJ 2193 이친수

- 문제 유형 : DP문제 내용0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.이친수는 0으로 시작하지 않는다.이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.입력첫째 줄에 N이 주어진다.출력첫째 줄에 N자리 이친수의 개수를 출력한다.예제 입력 13예제 출력 12풀이해당 자..

[프로그래머스] 소수 찾기 ( java )

문제 설명한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.1. 내 풀이에라토스테네스의 체를 이용했다. 문제 풀 당시 가장 효율적인 풀이는 기억이 안나서 원리만 간단히 차용해서 풀이했다.1) 에라토스테네스의 체를 만든다.2) dfs를 돌며 숫자를 만들고, 에라토스테네스의 체를 이용해 해당 수가 소수인지 확인한다음, 소수이면 Set에 넣는다.set은 순서 보장이 안되고 중복이 불가한 특징이 있다. 해당 문제에서는 set 안의 개수만 세면 되었기 때문에 그냥 사용했다...