목록PS/BOJ (214)
넘치게 채우기
https://www.acmicpc.net/problem/23300BOJ - 웹 브라우저 2문제 유형: 스택, 구현문제 난이도: Gold V시간 제한: 1초메모리 제한: 512MB 문제우리는 웹 페이지에 접속할 때 '웹 브라우저'를 사용한다. 웹 브라우저에는 크게 뒤로 가기(Backward), 앞으로 가기(Frontward), 웹페이지 접속(Access) 기능이 있다.사용자가 웹 사이트에 접속하면 컴퓨터의 캐시(cache)공간에 웹페이지 정보가 저장된다. 그리고 뒤로 가기 또는 앞으로 가기 기능을 사용하면 캐시 공간에 저장되어 있던 페이지의 정보를 불러오게 된다. 여기에 주헌이가 개발한 웹 브라우저에는 신기한 기능이 있는데, 바로 압축(Compress)이라는 기능이다. 압축 기능은 뒤로 가기 공간에 같은..
https://www.acmicpc.net/problem/28464BOJ - Potato문제 유형: 정렬, 그리디문제 난이도: Silver V시간 제한: 1초메모리 제한: 1024MB 문제감자튀김을 좋아하는 박 모 씨와 다르게, 성우는 감자튀김을 그렇게 좋아하지는 않는다. 어느 날 박 모 씨와 성우는 수많은 감자튀김을 받게 되었고, 이를 나누어 가지기로 했다.책상 위에 N$N$개의 접시가 놓여있다. i$i$번째 접시에는 ai$a_i$개의 감자튀김이 있다. 박 모 씨와 성우는 다음 행동을 번갈아 시행한다.책상 위에 남아있는 접시 하나를 고르고, 접시와 그 위에 놓인 모든 감자튀김을 가져간다.이는 책상 위의 접시가 모두 사라질 때까지 반복한다. 맨 처음 접시를 가져가는 사람은 박 모 씨다.박 모 씨는 가져가..
https://www.acmicpc.net/problem/2786BOJ - 상근이의 레스토랑문제 유형: 정렬, 그리디문제 난이도: Gold I시간 제한: 2초메모리 제한: 256MB 문제상근이는 도서관에서 번 돈으로 서강대 곤자가 플라자에 레스토랑을 하나 열었다. 이 레스토랑에는 음식을 N종류 팔고 있고, 손님은 서로 다른 음식을 여러개 시킬 수 있다. 이때, 음식을 시키는 순서가 중요하다. 그 이유는 각 음식을 첫 번째로 시킬 때의 가격과 아닐 때의 가격이 다르기 때문이다. 즉, 모든 음식 i의 가격은 첫 번째로 시킬 때의 가격 Ai와 아닐 때의 가격 Bi 두가지가 있다.배가 고픈 창영이는 상근이네 레스토랑에서 음식을 시켜먹으려고 한다. 이때, 1개, 2개, ..., N개 시킬 때 필요한 최소 가격을 ..
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를 제외한 소문자 알..