본문 바로가기

전체 글240

[BOJ] #3187 양치기 꿍 시간 제한 메모리 제한 정답 비율 1 초 128 MB 62.921% 3187번: 양치기 꿍 문제 양치기 꿍은 맨날 늑대가 나타났다고 마을 사람들을 속였지만 이젠 더이상 마을 사람들이 속지 않는다. 화가 난 꿍은 복수심에 불타 아예 늑대들을 양들이 있는 울타리안에 마구 집어넣어 양들을 잡아먹게 했다. 하지만 양들은 보통 양들이 아니다. 같은 울타리 영역 안의 양들의 숫자가 늑대의 숫자보다 더 많을 경우 늑대가 전부 잡아먹힌다. 물론 그 외의 경우는 양이 전부 잡아먹히겠지만 말이다. 꿍은 워낙 똑똑했기 때문에 이들의 결과는 이미 알고있다. 만약 빈 www.acmicpc.net 문제 양치기 꿍은 늑대들을 양이 있는 울타리 안에 마구 집어넣었다. 같은 울타리 영역 안의 양들의 숫자가 늑대의 숫자보다 더 많은 경.. 2019. 10. 13.
[BOJ] #7562 나이트의 이동 시간 제한 메모리 제한 정답 비율 1 초 256 MB 43.859% 7562번: 나이트의 이동 문제 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까? 입력 입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ... www.acmicpc.net 문제 체스판 위의 나이트를 몇 번 움직여 현재 위치에서 목적지까지 갈 수 있는지 횟 수를 출력하는 문제이다. 나이트의 이동을 인덱.. 2019. 10. 13.
[BOJ] #16236 아기 상어 시간 제한 메모리 제한 정답 비율 2 초 512 MB 36.088% 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다. 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크 www.acmicpc.net 문제 아기 상어가 먹을 수 있는 먹이 중 최단 거리에 있는 먹이를 차례대로 먹어야 한다. 이 때 최단 거리의 먹이가 여러개라면 가장.. 2019. 10. 11.
[BOJ] #17144 미세먼지 안녕! 시간 제한 메모리 제한 정답 비율 1 초 512 MB 54.847% 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다. 공기청정기는 항상 왼쪽 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼 www.acmicpc.net 해결방안 미세먼지 확산하는 단계, 공기가 순환하는 단계를 나눠서 구현하였다. 먼저 미세먼지가 확산하는 단계에서 유의해야할 점이.. 2019. 10. 10.
[BOJ] #14500 테트로미노 시간 제한 메모리 제한 정답 비율 2 초 512 MB 32.965% 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누 www.acmicpc.net 해결방법 기존 테트로미노에서 회전과 대칭된 모양까지 고려해야 했는데, 회전만 고려해서 문제를 풀었기 때문에 한 번 틀렸었다. 다음의.. 2019. 10. 10.
[BOJ] #13458 시험감독 시간 제한 메모리 제한 정답 비율 2 초 512 MB 24.464 % 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net 해결 방법 시험장 수와 각 시험장마다의 응시자 수가 입력으로 주어진다. 주어진 입력들을 배열 arr 에 저장하면, 임의의 시험장을 i 번째 시험장이라고 할 때 i 번째 시험장의 응시자 수는 arr[i] 이다. 각 arr[i]에 해당하는 응시자 수에 총 감독은 무조건 한 명만 있어야 하므로 총 감독이 감시할 수 있는 인원(B)을 뺀 값으로 .. 2019. 10. 9.
[BOJ] #2240 자두나무 시간 제한 메모리 제한 정답 비율 2 초 128 MB 35.371% 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어지는 자두를 받아서 먹고는 한다. 자두를 잡을 때에는 자두가 허공에 있을 때 잡아야 하는데, 이는 자두가 말랑말랑하여 바닥에 떨어지면 못 먹을 정도로 뭉개지기 때문이다. 매 초마다, 두 개의 나무 중 하나의 나무에서 열매가 떨어지게 된다. 만약 열매가 떨어지는 순간, 자두 www.acmicpc.net 문제 자두는 자두를 좋아한다. 자두가 떨어질 때까지 기다린 다음에 떨어지는 자두를 받아서 먹고는 한다. 자두가 허공에 있을 때 잡아야 .. 2019. 10. 2.
[BOJ] #2169 로봇 조종하기 시간 제한 메모리 제한 정답 비율 2 초 512 MB 31.977% 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net 방법 로봇이 '아래와 오른쪽'으로 가는 것과 '아래와 왼쪽'으로 가는 것 두 방법을 각각 구해서 더 큰 값으로 dp 배열을 채워나간다. 역시나.. dp는 통찰력!! 통찰력을 키우자ㅜㅜ 메모리 시간 9012 KB 124 ms 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34.. 2019. 10. 2.
[BOJ] #1149 RGB 거리 시간 제한 메모리 제한 정답 비율 0.5 초 128 MB 46.756% 1149번: RGB거리 RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이고, 첫 집과 마지막 집은 이웃이 아니다. 각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠하는 비용의 최솟값을 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 N개의 행에 대하여 해당 행(집)을 빨간색, 초록색, 파란색으로 칠할 때 드는 비용이 각각 주어진다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 .. 2019. 10. 2.

티스토리툴바