본문 바로가기

J 바로가기

🔥 PS(Problem Solving) 🔥122

[BOJ] #1012 유기농 배추 시간 제한 메모리 제한 정답 비율 1 초 512 MB 33.788% 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. ( www.acmicpc.net 문제 해충 방지에 효과적인 배추흰지렁이를 구입했다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히,.. 2019. 10. 14.

[BOJ] #10026 적록색약 시간 제한 메모리 제한 정답 비율 1 초 128 MB 57.637% https://www.acmicpc.net/problem/10026 10026번: 적록색약 문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 www.acmicpc.net 해결 방안 적록색약이 아닌 사람이 본 시선으로 나눠진 구역과, 적록.. 2019. 10. 13.

[BOJ] #1260 DFS와 BFS 시간 제한 메모리 제한 정답 비율 2 초 128 MB 30.405% https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. www.acmicpc.net 해결방안 각각 DFS와 BFS를 돌려서 출력하였다. 주의해야할 점은 간선은 양방향이라는 점! 메모리 시간 25568 KB 20 ms 123456789101112131415161718192021222324252627282.. 2019. 10. 13.

[BOJ] #11403 경로 찾기 시간 제한 메모리 제한 정답 비율 1 초 256 MB 51.358% 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 해결방안 각 정점에 대해 연결되어 있는 정점으로 DFS로 탐색하면서 지나갔다면 arr[i][j] 를 1로 바꾼다. 지나가지 않았던 정점에 대해서만 탐색을 계속 이어간다. 각 정점에 대해 연결되어 있는 정점의 정보를 알고 싶으므로 n 번 반복하면 모든 정점의 정보를 알 수 있다. 메모리 시간 2268 KB 0 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.. 2019. 10. 13.

[BOJ] #2589 보물섬 시간 제한 메모리 제한 정답 비율 1 초 128 MB 39.752% 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 이동은 상하좌우로 이웃한 육지로만 가능하며, 한 칸 이동하는데 한 시간이 걸린다. 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. 육지를 나타내는 두 곳 사이를 최단 거리로 이동하려면 같은 곳을 두 번 이상 지 www.acmicpc.net 해결방안 보물의 시작 점과 끝 점을 모르는 상태에서 가장 큰 육지의 끝과 끝의 최단거리를 구해야 하기 때문에 이중 for문을 돌리면서 모.. 2019. 10. 13.

[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.

이전 1 ··· 7 8 9 10 11 12 13 14 다음

티스토리툴바