백준

문제https://www.acmicpc.net/problem/1759 풀이문제에서 주어지는 조건은 다음과 같다.주어지는 알파벳의 개수가 최대 15개 ⇒ 완전탐색?주어지는 L개의 알파벳 중에 C개의 알파벳을 중복없이 고르기 ⇒ 순열? 조합?암호를 이루는 알파벳을 증가하는 순서대로 배열하기 ⇒ 입력받은 알파벳을 정렬하기암호는 최소 1개의 모음, 최소 2개의 자음으로 구성하기 ⇒ 가능성이 있는 암호인지 확인하기 위해 모음의 개수와 자음의 개수 세기a b c는 암호가 될 수 있지만 b a c는 암호가 될 수 없다. 이는 순서가 있는 것처럼 보여, 순열로 풀어야 한다고 생각할 수 있다. 하지만 알파벳이 정렬된 상태에서 고르는 것이므로, 현재 알파벳의 앞부분을 확인하지 않는다. 따라서 조합을 사용하면 된다. // ..

문제https://www.acmicpc.net/problem/16236 풀이이 문제는 조건이 많이 주어지기 때문에 조건을 잘 정리해야 한다.아기 상어는 자신보다 작은 크기의 물고기만 잡아먹을 수 있다.아기 상어는 자신보다 작거나 같은 크기의 물고기가 있는 칸으로만 이동할 수 있다.잡아먹을 물고기가 없다면 엄마 상어에게 도움을 요청한다.잡아먹을 물고기가 1마리라면 그 물고기를, 2마리 이상이라면 가장 가까운 거리에 있는 물고기를 잡아먹는다.거리가 같다면 가장 위에 있는 물고기를, 같은 높이라면 가장 왼쪽에 있는 물고기를 잡아먹는다. 가장 중요한 조건은 물고기를 잡아먹는 조건이다. 그냥 BFS 탐색을 수행해서 물고기까지의 최단 거리를 구하면 된다고 생각할 수 있지만, 물고기를 잡아먹는 조건이 3가지나 주어지..

문제https://www.acmicpc.net/problem/1005 풀이건설 순서 규칙이 있는 방향 그래프(사이클X)이므로 위상 정렬을 사용해서 문제를 풀 수 있다.  위상정렬 문제를 푸는 것처럼 문제를 풀면 되지만, 목표한 건물을 짓는데 걸리는 시간을 구하기 위해서는 각 건물을 짓는데 소요되는 시간을 기록해야 한다. 문제에서 주어진 예시를 보면, 4번 건물을 짓기 위해서는 2번, 3번 건물이 지어져있어야 하므로 두 건물을 짓는 시간 중 최대 시간만큼 기다려야 한다. 따라서 4번 건물을 짓기 위해서는 10초 + Max(1초, 100초) + 10초 = 120초가 소요된다. 이러한 로직을 위상정렬을 수행할 때 추가해서 문제를 풀면 된다. 자세한 내용은 코드를 참고하면 된다. 코드import java.io...

문제https://www.acmicpc.net/problem/14889 풀이N명을 N / 2명씩 두 개의 팀으로 나눠야 한다. 즉, N명 중에서 N / 2명을 고르는 것(순서 상관X)이므로 조합을 사용하면 된다.  DFS 메서드(재귀)를 통해 N / 2명을 다 고른 후, 스타트 팀의 능력치와 링크 팀의 능력치를 구해야 한다. N / 2명을 고를 때 이미 방문 처리를 했으므로 방문 처리한 것은 스타트 팀, 하지 않은 것은 링크 팀으로 구분하면 된다.스타트 팀: used[i] = true링크 팀: used[i] = false 스타트 팀과 링크 팀의 능력치를 계산한 후, 두 팀의 능력치 차이를 최소값과 비교해 갱신하면 된다. 코드import java.io.BufferedReader;import java.io...

문제https://www.acmicpc.net/problem/1937 풀이n이 500이라 모든 위치에서 DFS를 돌려 최대 길이를 구하면 시간 초과가 발생한다. 따라서 DP(메모이제이션)를 함께 사용해야 한다. 대나무 숲 정보를 저장하기 위한 배열 외에도 dp 배열을 하나 더 선언해서 각 위치에서 이동할 수 있는 칸의 최대 개수를 기록해야 한다. (+ 방문 확인 기능) 시간을 줄이기 위해서는 이미 탐색했던 곳을 다시 확인하지 않아야 하므로, dp 배열에 값이 이미 기록되어 있다면 그 값을 바로 반환하면 된다. 그렇지 않다면 현재 위치에서 네 방향을 모두 탐색해야 한다. 이때, dfs 메서드를 호출해서 다음 칸에서 이동할 수 있는 칸의 최대 개수를 구해야 한다. 그리고 그 값을 현재 위치의 dp 배열에 더..

문제https://www.acmicpc.net/problem/2477 여담처음에는 이동하는 발자국만 생각해서 2차원 배열에 방문한 위치를 표시하고 BFS 탐색을 수행하는 방식으로 진행했다.("전체 크기 - 사각형에 포함되지 않는 영역"을 구하면 된다고 생각했었다. 대체 뭔 생각으로 했는지...?) 두 번째는 큰 사각형에서 포함되지 않는 사각형을 빼면 될 것 같다고 생각했다. 최대 가로/세로, 최소 가로/세로 길이를 구해서 계산을 했는데 이는 너무 단편적으로만 생각을 해서 틀렸다. (포함되지 않는 작은 사각형이 포함되는 작은 사각형보다 클 수 있음..!)  결국 다른 풀이를 참고했는데 이렇게 쉽게 풀 수 있는 것을 틀린게 너무 아쉽다..🤦🏻‍♀️ 풀이주어진 밭에서 자라는 참외의 수는 (육각형의 넓이 *..

보호되어 있는 글입니다.

문제https://www.acmicpc.net/problem/1600 여담예전에 풀었던 문제라 그런지 푸는 방식을 약간 외워서 푼 느낌이다. 비슷한 유형의 문제가 나오면 좋겠지만 그럴 확률은 많지 않으니 다양한 BFS/DFS 문제를 접하도록 노력해야지..! 아무튼 이와 같이 기본 조건에 상태에 대한 조건이 추가적으로 있다면 "차원을 추가해서 각각의 상태를 관리"하면 된다는 것을 기억하자! 풀이맨 왼쪽 위에서 맨 오른쪽 아래로 이동하는 최단 거리를 찾는 것이므로 BFS 탐색을 수행하면 된다.  이때, 말처럼 이동하는 횟수에 따라 방문할 수 있는 지점이 달라지므로, 말이 이동한 횟수에 따라 각각 방문 처리를 해줘야 한다. 따라서 방문 처리 배열을 vistied[세로][가로][말처럼 이동한 횟수]와 같이 3차..

13549: 숨바꼭질 3🔗 문제 링크BFS 탐색으로 최소 시간을 구하면 됨순간이동은 0초, X+1 또는 X-1로 이동하는 것은 1초가 걸리므로 순간이동을 먼저 수행하는 것이 좋음더보기24.07.01 풀이import java.io.*;import java.util.*;public class Main { static final int MAX = 100_000; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br...

문제https://www.acmicpc.net/problem/1149 여담예전에 풀었을 때는 풀이를 참고해서 풀었는데 이번에는 스스로 풀었다..! 실력이 크게 는 것 같지는 않지만 그래도 좀 뿌듯 ㅎㅎ 근데 DP 문제라는 것을 알고 있어서 쉽게 풀었지, 몰랐다면 헤맸을 것 같다. 각 유형을 공부한 뒤에 랜덤으로 문제를 푸는 연습도 꼭 해야 되겠다..! 풀이모든 집을 칠하는 최소 비용을 구하기 위해 1번 집부터 N번 집을 칠하는 최소 비용을 누적하여 테이블을 채워 나가면 된다. 이때, 연속된 집은 같은 색으로 칠하지 못한다. 따라서 색칠하는 경우의 수는 다음과 같다.현재 집에 빨간색을 칠하는 경우이전 집은 초록색 또는 파란색이 칠해져 있어야 함dp[i][0] = Math.max(dp[i][1], dp[i]..