16236. 아기 상어 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 아이디어💡 1차시도 물고기 크기가 6가지 → 각 크기 별 남아있는 개수, 먹을 수 있는 물고기 개수 세면서 가기 → 먹을수있는게 없으면 끝 일반 멤버 변수 물고기 크기별 물고기 개수 저장: int[] 아기상어 객체 인스턴스 맵 현재 시간 먹을 수 있는 물고기 개수 초기는 크기 1인 물고기 개수 내부에 아기상어 클래스 생성 멤버 변수 위치 상어 크기 초기값 : 2 먹은 물고기 개수 기능 먹기 해당 위치의 물고기 크기에 대한 물고기 개수..
백준
20056. 마법사 상어와 파이어볼 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 아이디어💡 맵을 파이어볼 뭉치(파이어볼 리스트)를 갖게끔 해서 만들자! 필요한 클래스를 정해보자 좌표 파이어볼 좌표, 질량, 속도, 방향 움직였는지 여부 ⇒ move를 할 때 이동한 파이어볼 또 안돌리게! 파이어볼 뭉치 파이어볼 리스트 각 클래스 별로 필요한 메서드를 생각해보자 파이어볼 이동하기 파이어볼 뭉치 파이어볼 초기화(움직였는지 여부 초기화) 합치고 나누기 구현하자 1번 행은 N번과..
21610. 마법사 상어와 비바라기 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net 아이디어💡 상어 시리즈는 공통적으로 문제를 잘 읽고 제대로 구현하는걸 요구합니다. 따라서 다음과 같이 진행했습니다. 초기 설정 맵과 구름의 생성: N×N 크기의 맵과 초기 구름 위치가 설정됩니다. 구름은 특정 위치에 생성되며, 이후 이동, 비 내리기, 물 복사 버그 마법 등의 과정을 거치게 됩니다. 구름의 이동 방향과 속도: 사용자로부터 입력 받은 방향(d)과 속도(s)에 따라 구름이 이동합니다. 이때, 구름의 위치는 모..
4485. 녹색 옷 입은 애가 젤다지? 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 아이디어💡 처음에는 DFS(백트래킹)을 이용하는 방법을 생각했다. 하지만 시간초과가 나서 다익스트라를 활용하는 것으로 변경하니 성공했다. DFS (백트래킹) → 시간초과 결론 : 다익스트라 시간복잡도⌛ 우선 순위 큐 삽입 / 삭제 연산 : O(log N) -> 우선 순위에 모든 노드를 우선순위에 삽입 / 삭제 : O(N^2 * log(N)) 전체 코드 import java.io.BufferedReader;..
7579. 앱 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 아이디어💡 DP 초기화 각 앱의 메모리 사용량과 비활성화 비용을 저장하기 위한 Memory 객체 배열 memories를 생성합니다. DP 배열 정의 dp[j]를 메모리 j를 확보하기 위한 최소 비용으로 정의합니다. 이 배열은 최대 필요 메모리 M까지 고려하여 초기화됩니다. DP 초기화 첫 번째 앱을 사용하여 dp 배열을 초기화합니다. 첫 번째 앱의 메모리가 M을 넘지 않는 범위 내에서, 해당 앱의 비용으로 초기화합니다. DP 점화식 적용 만약 현재 살펴보..
2747. 피보나치 수 2747번: 피보나치 수 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 문제를 간단히 살펴보면, 수를 입력받아서 해당 순서에 맞는 피보나치 수를 반환하는 것이 목적이다. 이는 DP 접근법으로 해결할 수 있는 대표적인 문제다. 그 중 DP 바텀업 방식을 적용해 아래 순서부터 차근차근 DP 배열을 채워나갈 것이다. 점화식은 다음과 같다. dp[n] = dp[n-1] - dp[n-2] 전체 코드 import java.util.Scanner; public class Main { pub..
2839번: 설탕 배달 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 문제를 다시 정리해보면 다음과 같다. 사탕가게에 설탕을 정확히 N kg을 배달한다. N은 3이상 5,000이하의 자연수 봉지는 3kg, 5kg 두 가지가 있고, 최대한 적은 봉지로 가져가려고 한다. 몇 봉지를 가져가야할까? 이에 대한 아이디어는 두 가지를 떠올릴 수 있었다. 첫번째는 그리디 방식으로 푸는 것이다. 3보다 5로 나누었을 때, 봉지 개수를 줄일 수 있기 때문에, N이 5로 나누어질 때까지, 3을 계속 빼자 두번째는 DP를 생각했다. dp..
