문제 링크 https://www.acmicpc.net/problem/4781 4781번: 사탕 가게 각 테스트 케이스의 첫째 줄에는 가게에 있는 사탕 종류의 수 n과 상근이가 가지고 있는 돈의 양 m이 주어진다. (1 ≤ n ≤ 5,000, 0.01 ≤ m ≤ 100.00) m은 항상 소수점 둘째자리까지 주어진다. 다음 n개 www.acmicpc.net ◆문제 해결 및 설명◆ 문제 해설 : 사탕 가게에 있는 모든 사탕의 가격과 칼로리가 주어졌을 때, 어떻게 하면 칼로리의 합이 가장 크게 되는지를 구하는 프로그램을 작성하시오. 보자마자 DP를 사용한 배낭문제를 떠올렸고, 이와 다른점은 중복된 캔디를 넣을 수 있음을 파악하고 코드를 작성하였다. 가격이 소수형이라서 이를 정수로 처리하기 위해 100을 곱해주었..
문제 링크 https://www.acmicpc.net/problem/14497 14497번: 주난의 난(難) 주난이는 크게 화가 났다. 책상 서랍 안에 몰래 먹으려고 숨겨둔 초코바가 사라졌기 때문이다. 주난이는 미쳐 날뛰기 시작했다. 사실, 진짜로 뛰기 시작했다. ‘쿵... 쿵...’ 주난이는 점프의 파 www.acmicpc.net ◆문제 해결 및 설명◆ 문제 해설 : 생략 말이 좀 어려워서 애를 먹었는데(잘못된거 같기도) 예제를 보면 주난이와 이어진 0들의의 상하좌우를 0으로 만들어준다. 입력 예제 1번을 그림을 통해 표현해 보았다. 3번뛰면 (0,1)이 지워지면서 정답임을 알 수 있다. 일단, 교실의 정보를 저장할 변수 mapS과 위치정보(y10, x1, y2, x2)를 저장하고, 교실의 입력이 문자..
문제 링크 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 오늘의 생각 : 0 - 1 bfs를 배웠다. ◆문제 해결 및 설명◆ 문제 해설 : 0초가 걸리는 *2 순간이동과 1초가 걸리는 좌우1칸 이동을 통해 가장 빠르게 목적지(동생)에게 도착하자. 최단거리 문제중 가중치가 0또는 1이므로 다익스트라를 통해 풀 수 있겠다는 것을 알았지만, 최근 배운 0 - 1 bfs를 사용해 풀어보았다. 0 - 1 bfs는 ..
문제 링크 https://www.acmicpc.net/problem/1245 1245번: 농장 관리 첫째 줄에 정수 N(1 < N ≤ 100), M(1 < M ≤ 70)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄마다 격자의 높이를 의미하는 M개의 정수가 입력된다. 격자의 높이는 500보다 작거나 같은 음이 아닌 정수 www.acmicpc.net 오늘의 생각 : 문제를 잘 읽자! ◆문제 해결 및 설명◆ 문제 해설 : 산봉우리는 같은 높이를 가지는 하나의 격자 혹은 인접한 격자들의 집합으로 이루어져 있다. (여기서 "인접하다"의 정의는 X좌표 차이와 Y좌표 차이 모두 1 이하일 경우로 정의된다.) 또한 산봉우리와 인접한 격자는 모두 산봉우리의 높이보다 작아야한다. 문제는 격자 내에 산봉우리의 개수가 ..
