목표를 향해 천천히.. 목표를 향해 천천히..

--문제-- https://www.acmicpc.net/problem/16197 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net -- 문제 접근-- 사방탐색을 통하여 최소 이동으로 동전 하나만을 떨어뜨리는 문제이다. 두 개를 떨어뜨린다면 안되는 조건입니다. '10번 안으로 들어와야하는 조건'을 보고 기저조건을 10으로 사용하면 되겠다고 생각을 들었습니다. 그리하여 DFS로 문제풀이를 진행하였습니다. --코드-- package 최근빈출유형백준; import java.util.Scanner; public clas..

--문제-- https://www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net --문제 접근-- 문제 접근 처음에는 배열을 만들어 에라토스테네스 체를 만들어 검사를 하는 방식을 고려하였는데 메모리 제한이 4MB라서 포기하였습니다. 그다음으로 생각 한 것은 DFS를 통해 푸는 것입니다. 여기서 소수를 검사할 때 수의 제곱근까지만 검사를 합니다. 이유는 모든 수를 두 수의 곱으로 표현했을 때 각각의 두 수 중에 하나는 반드시 제곱 근 보다 작거나 같습니다..

--문제-- https://www.acmicpc.net/problem/1743 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다 www.acmicpc.net --문제접근-- 이 문제는 1303 전쟁과 비슷한 문제로 가로세로 연결된 것들 중 가장 큰 값을 구하는 문제였습니다. BFS를 활용하여 문제 풀이를 진행하였습니다. --코드-- package DFS와BFS기본문제; import java.util.LinkedList; import java.util.Queue; import java.util.Sca..

--문제-- https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net --문제 접근-- 문제는 가로세로에 우리팀이 있는지 확인하는 것입니다. 대각선을 고려하지 않습니다. 그리하여 최대 길이를 구한다음 제곱하여 더하면 되는 것 입니다. 저는 BFS로 풀었습니다. --코드-- package DFS와BFS기본문제; import java.util.LinkedList; import java.util.Queue; import java.ut..

--문제-- https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net --문제 접근-- 처음 문제를 봤을 때 중복 조합을 만들어 K를 만든다면 +1을 하여 답을 구하려 했는데 시간 초과가 나타났습니다. 다시 조건을 보니 당연한 시간 초과였습니다.. 그리하여 다르게 생각해본 결과 DP를 통해 문제를 푸는 방법을 고려하였습니다. 1.dp배열을 만듭니다. 2.dp [금액]=금액을 만드는데 가능한 경우의 수 3. dp [i]=dp [i]+dp [i-coin]입니..

--문제-- https://www.acmicpc.net/problem/1789 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net --문제 접근-- 문제는 서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까? 인데 간단하게 생각해보면 1부터 하나씩 차례대로 더해보다 만약 S보다 큰 값이 나온다면 그 값의 차이만큼만 빼면 S가 되므로 계속 더해주다가 -1만 해주면 된다고 생각하여 문제를 풀어 봤습니다. 만약 S가 200일 때 계속 더해주다가 201이 되었다고 가정해보자면 어차피 1만큼만 빼면 된다고 생각하였습니다. --코드-- package 기초백준추천문제; import java.util.Sc..

--문제-- https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net --문제 접근-- 문제풀이 생각 직관적으로 봤을 때 생각했던 문제풀이는 DFS로 접근하는 것을 생각해 봤습니다. 시작점과 도착점이 주어진다면 시작점에서 DFS를 모든 곳을 탐색해 본 이후 만약 도착점에 도착했을 때 값이 최소가 되는 값을 구하면 될 거라 생각했습니다. 여기서 고려해야 할 점은 boolean으로 이미 갔던 지역을 체크해 줘야 한다는 점입..

--문제-- https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net --문제 접근-- 그리디 탐색의 문제 N=멀티탭 구멍의 개수 K는 전기용품의 총 사용 횟수 두 번째 줄에는 전기용품의 이름 TC 1 2 7 2 3 2 3 1 2 7 고려해야할점 멀티탭의 개수, 나중에 이 용품이 다시 사용될 것인가? 이 두 가지를 중점적으로 생각해보기. 시나리오 1.멀티 탭이 여유롭다면 그냥 바로 꽂기 2. 여유가 없는데 만약 이미 꽂아진 전기용품이라면 그냥 skip ..