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

문제https://www.acmicpc.net/problem/1043 풀이진실을 아는 사람들과 같은 파티에 속하면 해당 파티에는 과장된 얘기를 할 수 없다. 즉, 진실을 아는 사람과 같은 파티에 속하는지를 확인하면 되는 문제이다. 따라서 유니온 파인드를 사용해서 그룹을 나눈 뒤, 같은 그룹에 포함되는지 확인하면 된다. 우선 진실을 아는 사람들을 같은 그룹으로 묶어야 한다.(union 메서드 호출) 편의상 첫 번째 사람을 대표자로 선정했다.  그 후, 파티의 정보를 입력받는다. 마찬가지로 같은 파티에 속하는 사람끼리 같은 그룹으로 묶는다. 이러한 과정을 반복하면 다음과 같이 된다.  이제 그룹을 다 나눴으므로 진실을 아는 사람과 같은 파티에 속하는지만 확인하면 된다. 각 파티의 대표자가 진실을 아는 그룹의..

문제https://www.acmicpc.net/problem/14500 풀이각 칸에서 DFS 탐색을 이용해서 4개 칸을 선택한 뒤, 선택한 배열의 합 중 최댓값을 찾으면 된다. 그냥 DFS 탐색을 이용해서 4개의 칸을 선택하면 ㅗ 모양을 처리할 수 없다는 문제가 발생한다. 그래서 총 2가지 방법을 사용해서 문제를 풀었다.  풀이 1첫 번째 방법은 DFS 탐색을 이용해서 3개의 칸을 선택한 뒤, 선택한 칸 주변의 칸 중 하나를 선택해서 최댓값을 고르는 것이다.  그러나 이 방법은 메모리를  너무 많이 잡아 먹어서 정석 풀이가 아닌 것 같다ㅎ.. 풀이 2두 번째 방법은 DFS 탐색을 이용해서 4개의 칸을 선택하고, DFS 탐색만으로 처리하지 못하는 ㅗ 방향을 따로 만들어서 확인해 주는 것이다. 이때, 회전과..

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

문제 SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 여담진짜 바보인가? 왜 자꾸 중요한 조건을 놓쳐서 틀리는걸까 ㅎㅎ.... 풀이 방식 잘 생각해놓고 이렇게 어이없이 틀릴 때마다 답답.. 제발 문제를 똑바로 다 읽고 정리하고 끝까지 확인하는 습관을 가지자!!! 풀이N의 범위(2 ≤ N ≤ 15)도 크지 않기 때문에 완전탐색 방식으로 문제를 풀었다. (다른 풀이를 찾아보니 BFS 방식으로도 풀 수 있는 듯 하다. 이건 나중에..) 가장 고려해야 할 부분은 소용돌이 장애물이다. 소용돌이 장애물은 2초마다 나타나고 1초 사라지는 형식을 띄고 있다.0초&1초: 나타남, 2초: 사라짐, 3초&4초: 나타남, 5초: 사라짐..

문제 SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 여담문제를 제대로 읽지 않았다..^^ 주변에 지뢰가 없는 것을 열면 끝이라고 생각했는데, 예시를 보니 "주변에 지뢰가 없는 것을 열었음 → 열은 칸 주변에도 지뢰가 없음 → 연속적으로 해당 칸 열기"를 하는 것이었다. 즉, BFS/DFS 탐색을 통해 푸는 문제였다...ㅎ 문제를 제대로 읽고 해석하는 것도 실력이니 꼭..! 문제를 꼼꼼히 읽자 풀이지뢰가 없는 칸을 모두 여는 최소 터치 횟수를 구하는 문제이고, 주변에 지뢰가 없는 것을 열었는데 새로 열은 칸 주변에도 지뢰가 없다면 연속해서 칸을 열어야 한다. 즉, 지뢰가 없는 칸을 여는 최소 터치 횟수 구하기 & ..

문제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]..

1463: 1로 만들기🔗 문제 링크1을 빼는 경우, 2로 나누는 경우, 3으로 나누는 경우를 각각 나누어서 점화식을 세워야 함1을 빼는 경우의 값으로 초기화: dp[i] = dp[i - 1]3으로 나누어지는 경우의 점화식: dp[i] = Math.min(dp[i], dp[i / 3] + 1)2로 나누어지는 경우의 점화식: dp[i] = Math.min(dp[i], dp[i / 2] + 1)BFS 탐색도 가능할 것 같아서 시도했는데 BFS 탐색으로도 최소 연산 횟수를 구할 수 있음탐색하고 있는 수가 1이 되면 탐색을 종료해야 함dist[N]이 아니라, dist[1]의 값이 N에서 1까지의 최소 연산 횟수이므로 주의할 것!더보기24.06.24 풀이DP 풀이import java.io.*;public clas..