본문 바로가기

전체 글

 (215)
백준 1937 욕심쟁이 판다 (Java) 1. 문제 링크 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. dfs 탐색으로만 하려다 크기가 큰 것 같아 이동 칸을 저장하기 위한 dp까지 함께 사용했다. 2. 모든 칸에서 dfs 탐색을 진행한다. 2-1. dp가 이미 채워져 있을 경우, 그 값을 반환한다. 2-2. 첫 방문일 경우, 한 칸을 뜻하는 1을 저장한다. 2-3. 사방 탐색을 하면서 지금보다 더 많은 대나무가 있는 곳으로 이동한다. 4. 코드 import java.io.BufferedRe..
백준 1647 도시 분할 계획 (Java) 1. 문제 링크 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. MST 문제로 크루스칼 알고리즘을 이용했다. 2. 노드를 가중치 기준으로 정렬한다. 3. 두 집이 연결되어 있지 않다면 연결한다. 4-1. 1번 코드는 전체를 다 연결하고 최대 연결 수까지의 값을 더한 것이다. 4-2. 2번 코드는 전체를 다 연결하고 최댓값 하나만 빼준 것이다. 4. 코드 import java.io.BufferedReader; import jav..
백준 18430 무기 공학 (Java) 1. 문제 링크 18430번: 무기 공학 첫째 줄에는 길동이가 가지고 있는 나무 재료의 세로, 가로 크기를 의미하는 두 자연수 N, M이 주어진다. (1 ≤ N, M ≤ 5) 다음 N개의 줄에 걸쳐서, 매 줄마다 나무 재료의 각 위치의 강도를 나타내 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. DFS 탐색을 통해 만들 수 있는 모든 부메랑의 경우를 찾는다. 2. 방문하지 않은 곳에서 만들 수 있는 4가지 부메랑을 만들어본다. 2-1. 각 부메랑의 조건을 통과하면 방문처리 후 dfs를 진행한다. 2-2. DFS가 끝나고 돌아오면 방문처리를 다시 원래대로 돌려둔다. (다른 경우에 영향 끼치지 않도록) 4. 코드 import java.io.BufferedReader; import..
백준 2156 포도주 시식 (Java) 1. 문제 링크 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. dp로 풀었다. 2. 2번째 잔까지는 3연속을 신경쓰지 않아도 되기에 더한 값을 넣는다. 3. 3번째 잔 부터는 연속 3개가 안되기 때문에 비교하여 더 큰 값을 저장했다. 3-1. 지금잔을 선택하지 않는 경우 3-2. 하나 앞의 잔을 선택하지 않고, 지금 잔을 선택하는 경우 3-3. 두개 앞의 잔을 선택하지 않고, 하나 앞의 잔과 지금 잔을 선택하는 경우 4. 코드 import java.io.Buffe..
백준 12886 돌 그룹 (Java) 1. 문제 링크 12886번: 돌 그룹 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. A, B, C를 입력받고, 만들 수 있는 돌 개수로 2차운 배열을 만든다. 2. 3 그룹의 합이 3의 배수가 아니라면 같은 개수로 나눌 수 없다. 3. DFS 탐색을 진행하며 A, B, C가 같은 개수가 나오는지 확인한다. 3-1. A와 B, B와 C, C와 A를 각 단계에서 전부 비교해보면서 나오는지 확인한다. 3-2. 방문 배열을 통해 작은 값과 큰 값이 나왔었는지 확인하고, 그 값들로 DFS..
백준 14442 벽 부수고 이동하기 2 (Java) 1. 문제 링크 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. 입력을 받고 시작 위치인 0,0에서 부순 벽 개수 0으로 시작한다. 2. BFS로 돌면서 방문 처리를 한다. (해당 위치에서 몇개의 벽을 부쉈는지 확인) 3. size만큼 반복하면서 이동 거리를 더한다. 4. 큐에서 하나씩 뺀다. 4-1. 뺀 위치가 종료 위치라면 끝낸다. 4-2. 아니라면 사방탐색을 진행한다. 4-3. 해당 위치에 벽이 없으면 현재 부순 벽 개수로 ..
백준 2166 다각형의 면적 (Java) 1. 문제 링크 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. 다각형의 면적은 삼각형으로 나눠서 구할 수 있다. 2. 다각형을 이루는 순서대로 주어지기 때문에 반복문을 통해 구했다. 3. 첫번째 점을 기준으로 2개씩 순서대로 고르면서 삼각형의 면적을 구했다. 4. 답이 음수가 나오는 경우가 있어 절댓값으로 출력했다. +) 값의 범위를 생각하면 int가 아니라 long으로 구해야 한다는 것을 주의하자 4. 코드 import java.io.BufferedReader; import java.i..
백준 14620 꽃길 (Java) 1. 문제 링크 https://www.acmicpc.net/problem/14620 14620번: 꽃길 2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다. 진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. 입력받은 칸의 수 중에서 조합으로 3칸을 고른다. 1-1. 전체 칸 수에서 조합으로 뽑은 수를 N으로 나눴을 때 몫이 행, 나머지가 열을 뜻한다. 2. 3칸을 사방탐색하면서 5칸을 방문한다. 2-1. 방문했을 때, 화단을 넘어가거나 방문했을 경우에는 끝낸다. 2-2. 총합이 지금의 최솟값을 넘으면 끝낸다. 3. 다 돌고 최솟값을 출력..

티스토리툴바