📝문제 💡풀이동적 계획법의 기본이 피보나치 수열인데 피보나치 수열의 함수가 주어지고 출력되는 1과 0의 개수를 구하라니, 이 또한 규칙이 있겠다고 생각했다.N0출력1출력101201312423N별로 출력값을 구해보니 dp[N][0] = > N이 호출 됐을 때 0 출력 개수dp[N][1] => N이 호출 됐을 때 1 출력 개수 라고 하면dp[N][0] = dp[N-2][0] + dp[N-1][0]dp[N][1] = dp[N-2][1] + dp[N-1][1] 의 규칙을 가지는 것을 확인했다. 전체 풀이import java.io.*;class Main{ public static void main(String[] args) throws IOException { BufferedReader br..

📝문제 💡풀이1. 시작한 시간을 기준으로 오름차순 정렬한다. 2. 첫 시간은 어차피 1개의 회의실을 써야하므로 room = 1로 시작3. 시작한 시간의 끝나는 시간을 우선순위 큐에 넣음4. 큐에 들어간 첫번째 값(종료시간)과 현재 시작 시간을 비교해서 시작 시간이 종료 시간보다 작을 때 회의실을 같이 쓸 수 없다. -> room++5. 시작 시간이 종료 시간보다 크거나 같을 때 회의실을 같이 쓸 수 있다 -> 큐에서 종료시간을 꺼내줌import java.util.*;import java.io.*;class Main{ public static void main(String[] args) throws IOException { BufferedReader br = new BufferedRe..

📝문제 💡풀이우선 서류 심사를 기준으로 오름차순을 한 후 1 42 53 64 25 76 17 3 서류 1등은 무조건 통과니까서류 2등부터 면접 성적 순위가 이전순위의 최솟값보다 크다면 인원수를 줄여주는 방식을 채택하였다.1 42 5  최솟값: 4 => 5가 4보다 큼3 6  최솟값: 4 => 6이 4보다 큼4 25 7 최솟값: 2 => 7이 2보다 큼6 17 3 최솟값:1 => 3이 1보다 큼면접 성적 순위는 숫자가 작은 것이 비교대상이 된다.import java.util.*;import java.io.*;class Main{ public static void main(String[] args) throws IOException { BufferedReader br = new Buff..

📝문제https://www.acmicpc.net/problem/17503 💡풀이선호도의 합이 M이상이고마신 맥주가 N개를 만족해야한다. 1) 맥주 도수 레벨을 기준으로 배열을 오름차순하고2) 우선순위 큐에 선호도 기준으로 오름차순한다.3) 배열을 돌려 차례대로 우선순위 큐에 저장하고4) 큐 사이즈가 N개가 되면 큐에 들어간 선호도 합을 계산한다.4-1) 선호도 합이 M이상이면 현재 맥주의 도수 레벨이 정답이 되므로 반복문을 빠져나온다.4-2) 선호도 합이 M 미만이면 다시 3)으로 돌아가서 가장 작은 선호도를 가진 맥주를 큐에서 빼낸다.M 미만이면 바로 큐에서 빼지 않는 이유: 다음 선호도가 현재 최소 선호도보다 작을 수 있음!import java.util.*;import java.io.*;class..

📝문제https://www.acmicpc.net/problem/11399 💡풀이모든 사람이 돈을 인출하는데 필요한 시간을 최적화하기 위해서는 시간이 적게 걸리는 사람부터 처리하면 된다.현재 상황에서의 최적의 값을 선택하면 전체 최적의 해가 된다 => 그리디 알고리즘 각 사람이 돈을 인출하는데 걸리는 시간을 오름차순으로 정렬 후 시간의 합을 구해준다. 전체 풀이import java.util.*;import java.io.*;class Main{ public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); ..

📝문제https://www.acmicpc.net/problem/27961 💡풀이문제엔 0마리 이상 k마리 이하의 고양이를 추가할 수 있다고 나와있지만 실제 필요한 수는 k마리라는 것이 핵심이다!N보다 커질 때 까지 (현재 고양이 수 x 2)를 해준다. 현재 고양이 수가 int의 범위를 넘어갈 수 있으므로 long으로 선언해야한다. 전체풀이import java.io.*;class Main{ public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); long N = Long.parseLong(br..

📝 문제https://www.acmicpc.net/problem/15686💡 풀이1) 치킨 집과 집을 ArrayList에 추가한다.for (int i = 0; i  2) M개의 치킨집을 선별한다.public static void selectChickens(int startIndex, int count) { if (count == M) { answer = Math.min(calculateDistance(selected), answer); return; } for (int i = startIndex; i  3) 집에서 가장 가까운 치킨 집을 찾는다.private static int calculateDistance(List selectedChickens) { ..

https://www.acmicpc.net/problem/2615  오늘도.. 시간을 save 하지 못했다..ㅜ 오목 문제라 문제 자체를 이해하는 데는 무리 없었지만 이를 구현함에 있어서 여러 고비가 있었다 8방향을 모두 검사하려 했으나 어차피 왼쪽 가장 첫 번째 돌만 구하면 되니 오른쪽 위, 오른쪽, 오른쪽 아래, 아래 방향만 검사한다. 재귀를 돌릴 때도 같은 방향에서만 돌린다. 가장 골치아팠던 문제는 육목 검사였다.같은 방향에서 길이가 5가 나오면 오목이거나 오목 이상이거나 인데둘의 차이점은 반대방향에 같은 돌이 있느냐 없느냐이다.그래서 나는 현재 위치 기준 반대 방향으로 한 칸만 검사해서 해당 돌이 현재 돌과 같은 색이면 육목 처리를 해주었다. 이렇게 하고도 25%에서 틀렸다고 나왔는데... 문제를..

https://www.acmicpc.net/problem/2529역대급 오래 걸린 문제🤦‍♀️3년 전에 내가 푼 풀이를 참고하여 겨우 정답을 맞혔다 "">"부호가 올 때는 현재 수보다 무조건 작은 값이 오는 게 핵심이다!! 현재수를 current, 정답을 각 자리 수마다 넣어줄 배열 (arr)의 현재 인덱스를 index로 사용해 줄 것이다. current = 0, index = 1 (부등호 배열과 함께 쓰기 위해 1부터 시작)부터 시작한다.이때, arr [0] = current로 초기화해 준다. 부등호가 "현재 수 보다 큰 1부터 9까지 arr [1]에 들어갈 수 있고재귀로 dfs(1,2) 이렇게 다음 경우의 수를 호출한다.백트래킹을 해서 모든 경우의 수를 찾아야 하므로 재귀 호출 후 방문 배열을 다시..

https://www.acmicpc.net/problem/1051반례를 찾느라 진빠졌던 문제다;완전탐색이라고 생각하고 풀면 어렵지 않다. 왼쪽 위 부터 오른쪽 아래까지 모두 검사하며 정사각형을 구한다.배열로 치면arr[0][0]~arr[N-1][M-1] 까지 만약 세로줄에서 같은 수를 찾았다면 가로줄에서 같은 값이 있는지 찾는다.이렇게 총 4개의 점에 대해 검사를 해야한다.public static int rectangle(int a, int b){ int n = arr[a][b]; int h,w; int area = 0; for(int i = a+1; i arr[i][j] == n 부분을 빼먹고 맞는데 왜 틀리지? 라고 생각했으나역시 컴퓨터는 나보다 정확하다내가 놓친 반례는 아래의 ..