본문 바로가기

백준68

[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.
[BOJ] #1010 다리놓기 시간 제한 메모리 제한 정답 비율 2 초 128 MB 47.942% 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 방법 'dp[i][j]는 서쪽에 i 개의 점이 있고, 동쪽에 j 개의 점이 있다고 했을 때 놓을 수 있는 다리의 수' 라고 정의를 해보았다.그리고 그림을 그려봤는데, 같은 i개의 점일 때는 j값에 따라 같은 모습의 다리들이 반복되는 것을 볼 수 있었고 왼쪽 상단에 보이듯이 표를 채워보니 아래와 같은 규칙을 찾아낼 수 있었다. 그래서 식을 세워보면 이렇게 된다. i == 1 dp[i][j] = j.. 2019. 10. 2.
[BOJ] #14891 톱니바퀴 시간 제한 메모리 제한 정답 비율 2 초 512 MB 49.598% 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴가 1번, 그 오른쪽은 2번, 그 오른쪽은 3번, 가장 오른쪽 톱니바퀴는 4번이다. 이때, 톱니바퀴를 총 K번 회전시키려고 한다. 톱니바퀴의 회전은 한 칸을 기준으로 한다. 회전은 시계 방향과 반시계 방향이 있고, 아래 그림과 같이 회전한다. 톱니바퀴를 회전시키려 www.acmicpc.net 방법 톱니바퀴들을 gears 라는 배열에 저장해 두고 회전시킬 톱니바퀴를 gear 라고 했을 때, gear 기준으로 왼쪽 톱니바퀴들과.. 2019. 10. 2.
[BOJ] #14889 스타트와 링크 시간 제한 메모리 제한 정답 비율 2 초 512 MB 50.576% 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 방법 1 : vector 이용 Brute Force 로 스타트팀의 구성원을 구해고, 스타트팀의 구성원을 기반으로 링크팀의 구성원을 알아낸다. 그렇게 팀의 구성원을 알아낸 후에 각 팀의 능력치를 계산하여 비교하고 MIN 값을 매번 갱신시킨다. 함수 설명 인자 idx는 인덱스 순서를 나타내고, cnt 는 스타트팀의 구성원이 아닌 사람의 숫자이다. 스타트팀과 링크팀의 구성원은 무조건 n/2 명이므로 스타트팀의 구성원이 아닌.. 2019. 10. 2.

티스토리툴바