넘치게 채우기

https://www.acmicpc.net/problem/1926BOJ - 그림문제 유형: 그래프, bfs, 연결 컴포넌트문제 난이도: Silver I시간 제한: 2초메모리 제한: 128MB 문제어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다. 입력첫째 줄에 도화지의 세로 크기 n(1 ≤ n ≤ 500)과 가로 크기 m(1 ≤ m ≤ 500)이 차례로 주어진다. 두 번째 줄부터 n+1 줄 까지 그림의 정보가 주어진다. (단 그림의 정보는 0과..

https://www.acmicpc.net/problem/5014BOJ - 스타트링크문제 유형: 그래프, bfs문제 난이도: Silver I시간 제한: 1초메모리 제한: 256MB 문제강호는 코딩 교육을 하는 스타트업 스타트링크에 지원했다. 오늘은 강호의 면접날이다. 하지만, 늦잠을 잔 강호는 스타트링크가 있는 건물에 늦게 도착하고 말았다.스타트링크는 총 F층으로 이루어진 고층 건물에 사무실이 있고, 스타트링크가 있는 곳의 위치는 G층이다. 강호가 지금 있는 곳은 S층이고, 이제 엘리베이터를 타고 G층으로 이동하려고 한다.보통 엘리베이터에는 어떤 층으로 이동할 수 있는 버튼이 있지만, 강호가 탄 엘리베이터는 버튼이 2개밖에 없다. U버튼은 위로 U층을 가는 버튼, D버튼은 아래로 D층을 가는 버튼이다. ..

https://www.acmicpc.net/problem/2573BOJ - 빙산문제 유형: bfs, 구현, 시뮬레이션문제 난이도: Gold IV시간 제한: 1초메모리 제한: 256MB 문제지구 온난화로 인하여 북극의 빙산이 녹고 있다. 빙산을 그림 1과 같이 2차원 배열에 표시한다고 하자. 빙산의 각 부분별 높이 정보는 배열의 각 칸에 양의 정수로 저장된다. 빙산 이외의 바다에 해당되는 칸에는 0이 저장된다. 그림 1에서 빈칸은 모두 0으로 채워져 있다고 생각한다.        2453   3 252  7624         그림 1. 행의 개수가 5이고 열의 개수가 7인 2차원 배열에 저장된 빙산의 높이 정보빙산의 높이는 바닷물에 많이 접해있는 부분에서 더 빨리 줄어들기 때문에, 배열에서 빙산의 각 부..

https://www.acmicpc.net/problem/1660BOJ - 캡틴 이다솜문제 유형: 다이나믹 프로그래밍문제 난이도: Gold V시간 제한: 2초메모리 제한: 128MB 문제캡틴 이다솜은 자신의 해적선에 적을 공격하기 위한 대포알을 많이 보관해 놓는다. 다솜이는 미적감각이 뛰어나기 때문에, 대포알은 반드시 사면체 모양으로 쌓아놓아야 한다고 생각한다. 사면체를 만드는 방법은 길이가 N인 정삼각형 모양을 만든다. 그 위에 길이가 N-1인 정삼각형 모양을 얹고 그위에 계속 해서 얹어서 1크기의 정삼각형 모양을 얹으면 된다.예를 들어, 사이즈가 3크기의 한 더미 모양은 다음과 같다. X X X X X X XX X X각각의 삼각형은 1, 3, 6, 10 ,..... 와 같이 대포알을 가지고 있다..

https://www.acmicpc.net/problem/18116BOJ - 로봇 조립문제 유형: 유니온-파인드, 분리 집합문제 난이도 : Gold IV시간 제한: 4초메모리 제한: 1024MB 문제성규는 로봇을 조립해야 한다. 상자 안에는 여러 로봇의 부품들이 섞여 있다. 그런데 어떤 부품이 어느 로봇의 부품인지 표시가 되어있지 않다. 호재는 전자과라서 두 부품을 보면 같은 로봇의 부품인지 알 수 있다. 그래서 성규는 호재의 지시에 따라 부품들을 정리하기로 하였다.부품들은 1부터 106까지의 정수로 표현된다. 그리고 부품 i가 속한 로봇은 robot(i)라고도 표현한다. 예를 들어, 부품 11과 부품 22가 로봇 A의 부품이라고 알고 있는 경우, robot(11)은 로봇 A를 의미하고, robot(22..

https://www.acmicpc.net/problem/21319BOJ - 챔피언(Easy)문제 유형: 그리디, 이분 탐색, 시뮬레이션문제 난이도: Gold I시간 제한: 2초메모리 제한: 1024MB 문제입력 조건 외 챔피언 (Hard)와의 차이는 없다.민겸이는 세계적인 격투기 선수 육성 회사의 회장이다. 민겸이는 격투기 선수의 영입을 위해 세계 격투기 챔피언십을 관람하기로 했다. 세계 격투기 챔피언십의 규칙은 아래와 같다.격투기 선수는 N명이고, 일렬로 서 있다. 선수들은 각각 전투력을 가지고 있다. 격투기 선수들은 양쪽으로 이웃한 두 명의 선수들 중 한 명에게 싸움을 걸어 격투를 벌인다. 이 때, 전투력이 높은 격투기 선수가 승리한다. 격투에서 승리한 선수는 자신감이 붙어 전투력이 1 증가한다. ..

https://www.acmicpc.net/problem/33516BOJ - skeep 문자열문제 유형: 문자열 처리, 스택문제 난이도: Gold III시간 제한: 1초메모리 제한: 1024MB 문제skeep은 자신의 오프라인 팬클럽을 운영 중이다. 어느덧 인기스타가 된 skeep의 팬클럽에는 사람들이 몰려 공간이 부족해졌다.이에 skeep은 자신의 진정한 팬만 팬클럽에 입장시키기로 결심했다.skeep의 진정한 팬이라면 skeep이라는 문자열을 좋아할 것이라 믿으며, 이를 판별하기 위해 다음과 같은 문제를 준비했다.길이가 N$N$인 알파벳 소문자로 구성된 문자열이 주어진다. 이 문자열에서 다음 작업을 원하는 만큼 수행할 수 있다.문자열에서 skeep이라는 연속한 부분 문자열을 찾아 s를 제외한 소문자 알..

https://www.acmicpc.net/problem/2224BOJ - 명제 증명문제 유형: 플로이드-워셜, 문자열 처리문제 난이도: Gold IV시간 제한: 2초메모리 제한: 128MB 문제수학, 혹은 논리학에서 만약 무엇 이라면 뭣 일 것이다 하는 식의 명제가 널리 쓰인다. 예를 들어 "P이면 Q일 것이다." 라는 명제는 “P => Q” 라는 기호로 표현된다. 이때의 P를 전건, Q를 후건이라고 한다.논리학에서 어떤 명제를 증명할 때 가장 널리 쓰이는 방법 중 한 가지가 바로 삼단 논법이다. 만약 두 명제 “P => Q", "Q => R" 가 모두 참이면, 명제 "P => R"이 역시 참이 된다. 이러한 방법을 사용했을 때 명제 ”P => R"이 증명되었다고 한다.어떤 참인 명제가 주어졌을 때, ..

https://www.acmicpc.net/problem/17619 BOJ - 개구리 점프문제 유형: 분리 집합, 유니온 파인드, 정렬문제 난이도: Gold III시간 제한: 1초메모리 제한: 512MB 문제통나무 N개가 가로 (수평) 방향으로 연못에 떠 있다. 개구리는 한 통나무 A에서 다른 통나무 B로 정확히 수직 방향으로 점프할 수 있다. 단, 점프할 때 다른 통나무 위를 (끝 점 포함) 지나면 안된다.예를 들어 에서 1번 통나무에서 2번 통나무로 점선을 따라 개구리가 점프하는 것이 가능하다. 1번 통나무에서 2번 통나무로 점프한 후 다시 3번 통나무로 점프하면 1번 통나무에서 3번 통나무로 이동하는 것이 가능하다. (통나무 위에서 걸어서 움직이는 것은 언제든 가능하다.) 통나무들의 위치를 입력받아..

https://www.acmicpc.net/problem/20168BOJ - 골목 대장 호석 - 기능성문제 유형: 그래프, 최단경로, 브루트 포스문제 난이도: Gold V시간 제한: 3초메모리 제한: 512MB 문제소싯적 호석이는 골목 대장의 삶을 살았다. 호석이가 살던 마을은 N 개의 교차로와 M 개의 골목이 있었다. 교차로의 번호는 1번부터 N 번까지로 표현한다. 골목은 서로 다른 두 교차로를 양방향으로 이어주며 임의의 두 교차로를 잇는 골목은 최대 한 개만 존재한다. 분신술을 쓰는 호석이는 모든 골목에 자신의 분신을 두었고, 골목마다 통과하는 사람에게 수금할 것이다. 수금하는 요금은 골목마다 다를 수 있다.당신은 A 번 교차로에서 B 번 교차로까지 C 원을 가지고 가려고 한다. 호석이의 횡포를 보며..