분류 전체보기 (215) 썸네일형 리스트형 백준 1012 유기농 배추 (Java) 1. 문제 링크 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 배추가 나오면 bfs를 시작해서 인접한 배추를 전부 방문처리한다. bfs를 한 번 할 때마다 배추의 개수를 증가한다. 4. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.Queue; import java.io.IOException; public class Main.. 백준 1331 나이트 투어 (Java) 1. 문제 링크 1331번: 나이트 투어 나이트 투어는 체스판에서 나이트가 모든 칸을 정확히 한 번씩 방문하며, 마지막으로 방문하는 칸에서 시작점으로 돌아올 수 있는 경로이다. 다음 그림은 나이트 투어의 한 예이다. 영식이는 6× www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 나이트의 이동 범위인지 확인하는 과정이 필요하다. 전에 있던 좌표와 x축 절댓값 차이가 2이면서 y축 절댓값 차이가 1인 경우거나 x축 절댓값 차이가 1이면서 y축 절댓값 차이가 2인 경우인지 판단한다. 또한 방문했던 좌표인지 확인하는 과정도 필요하다. 그 과정에서 flag가 바뀌었는지 판단해서 "Valid" 또는 "Invalid"를 출력한다. 4. 코드 import java.io.BufferedReader;.. 백준 7562 나이트의 이동 (Java) 1. 문제 링크 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 나이트가 움직이는 8방향으로 bfs 탐색을 진행한다. 최소 횟수로 움직여야 하기 때문에 방문했는지 확인하기 위해 visit 배열을 이용했다. 사실 1331번 나이트 투어를 풀려고 하는데 나이트가 어떻게 움직이는지 몰라서 이 문제를 먼저 찾아왔다...ㅎ 4. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util... 백준 4485 녹색 옷 입은 애가 젤다지? (Java) 1. 문제 링크 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 그냥 풀어도 통과는 하지만 dp로 풀었을 때 메모리와 시간 측면에서 훨씬 향상된 모습을 볼 수 있다. 1번 풀이는 완전탐색이고 215676KB 792ms 라는 결과가 나왔다. 2번 풀이는 dp 이고 17848KB 180ms라는 결과가 나왔다. 4. 코드 1. 1번 풀이 import java.io.BufferedReader; import java.io.InputStreamReader; im.. 백준 4963 섬의 개수 (Java) 1. 문제 링크 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 8방으로 bfs 탐색을 진행한다. 섬의 시작이 어디부터인지 몰라서 8방으로 진행했다. 4. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.Queue; import java.io.IOException; public class Main { stati.. 백준 2580, 2239 스도쿠 (Java) 1. 문제 링크 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 두 문제가 입출력의 공백 차이 뿐이라 함께 가져왔다. dfs 느낌으로 이 숫자일 때 다음 숫자가 가능한지 그 다음은 가능한지... 의 순서로 코드를 진행한다.. 백준 1194 달이 차오른다, 가자 1. 문제 링크 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 비트마스킹을 해야 하는 문제라 조금 어려웠다. 시작점부터 BFS 하면서 해당 위치가 벽/열쇠/문/출구인지에 따라 다른 조건문에 들어간다. 출구가 나오면 최댓값을 갱신하고 return한다. 빈 칸인 경우에는 갈 수 있는 곳이므로 queue에 넣는다. 열쇠가 나올 경우 비스마스킹으로 키를 추가하고 갈 수 있는 곳이므로 queue에 넣는다. 대문자일 경우 해당 문자열을 키가 가지고.. 백준 2632 피자 판매 (Java) 1. 문제 링크 2632번: 피자판매 첫 번째 줄에는 손님이 구매하고자 하는 피자크기를 나타내는 2,000,000 이하의 자연수가 주어진다. 두 번째 줄에는 A, B 피자의 피자조각의 개수를 나타내 는 정수 m, n 이 차례로 주어진다 (3 ≤ m, n www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 피자 조각별 크기를 입력받고 저장하면서 총 크기를 저장한다. 연속적으로 피자 조각을 더해야 하기 때문에 DP 느낌으로 생각했다. 시작 숫자에 따라 연속적으로 이어질 때 항상 마지막 경우는 피자 전체를 의미하기 때문에 뺐다. 피자 전체 조각에서 i+j를 나눠서 배열을 2배 길게 넣은 느낌으로 풀었다. 그때 나온 값이 원하는 크기보다 작으면 해당 크기의 dp를 한다. 두 피자로 각각 만들 .. 이전 1 ··· 7 8 9 10 11 12 13 ··· 27 다음
