백준 1948 - 임계경로 시간 제한 2초, 메모리 제한 512MB # 조건 월드 나라는 모든 도로가 일방통행인 도로이고, 싸이클이 없다. 그런데 어떤 무수히 많은 사람들이 월드 나라의 지도를 그리기 위해서, 어떤 시작 도시로부터 도착 도시까지 출발을 하여 가능한 모든 경로를 탐색한다고 한다. 이 지도를 그리는 사람들은 사이가 너무 좋아서 지도를 그리는 일을 다 마치고 도착 도시에서 모두 다 만나기로 하였다. 그렇다고 하였을 때 이들이 만나는 시간은 출발 도시로부터 출발한 후 최소 몇 시간 후에 만날 수 있는가? 즉, 마지막에 도착하는 사람까지 도착을 하는 시간을 의미한다. 어떤 사람은 이 시간에 만나기 위하여 1분도 쉬지 않고 달려야 한다. 이런 사람들이 지나는 도로의 수를 카운트 하여라. 출발 도시는..

백준 16564 - 히오스 프로게이머 시간 제한 2초, 메모리 제한 512MB # 조건 성권이는 Heroes of the Storm 프로게이머 지망생이다. 이 게임에는 총 N개의 캐릭터가 있다. 그리고 현재 각 캐릭터의 레벨은 Xi이다. 성권이는 앞으로 게임이 끝날 때까지, 레벨을 최대 총합 K만큼 올릴 수 있다. 팀 목표레벨 T =min(Xi) (1 ≤ i ≤ N)라고 정의하면, 게임이 끝날 때까지 성권이가 달성할 수 있는 최대 팀 목표레벨 T는 무엇인가? 예를 들어, N = 3, X1= 10, X2= 20, X3= 15이고 K = 10일 때, X1을 7만큼 올리고 X3을 2만큼 올리면 최소 레벨 Xi는 17이 된다. 라서 팀 목표레벨 T는 17이다. 이 경우처럼 레벨을 총합 K보다 적게 올릴 수도 있..

백준 9342 - 염색체 시간 제한 2초, 메모리 제한 64MB # 조건 상근이는 생명과학 연구소에서 염색체가 특정한 패턴인지를 확인하는 일을 하고 있다. 염색체는 알파벳 대문자 (A, B, C, ..., Z)로만 이루어진 문자열이다. 상근이는 각 염색체가 다음과 같은 규칙을 만족하는지 검사해야 한다. 문자열은 {A, B, C, D, E, F} 중 0개 또는 1개로 시작해야 한다. 그 다음에는 A가 하나 또는 그 이상 있어야 한다. 그 다음에는 F가 하나 또는 그 이상 있어야 한다. 그 다음에는 C가 하나 또는 그 이상 있어야 한다. 그 다음에는 {A, B, C, D, E, F} 중 0개 또는 1개가 있으며, 더 이상의 문자는 없어야 한다. 문자열이 주어졌을 때, 위의 규칙을 만족하는지 구하는 프로그램을..

백준 19236 - 청소년 상어 시간 제한 1초(추가 시간 없음), 메모리 제한 512MB # 조건 아기 상어가 성장해 청소년 상어가 되었다. 4×4크기의 공간이 있고, 크기가 1×1인 정사각형 칸으로 나누어져 있다. 공간의 각 칸은 (x, y)와 같이 표현하며, x는 행의 번호, y는 열의 번호이다. 한 칸에는 물고기가 한 마리 존재한다. 각 물고기는 번호와 방향을 가지고 있다. 번호는 1보다 크거나 같고, 16보다 작거나 같은 자연수이며, 두 물고기가 같은 번호를 갖는 경우는 없다. 방향은 8가지 방향(상하좌우, 대각선) 중 하나이다. 오늘은 청소년 상어가 이 공간에 들어가 물고기를 먹으려고 한다. 청소년 상어는 (0, 0)에 있는 물고기를 먹고, (0, 0)에 들어가게 된다. 상어의 방향은 (0, ..

백준 18311 - 왕복 시간 제한 1초, 메모리 제한 256MB # 조건 왕복 달리기 선수는 N개의 이어진 일직선상의 코스들을 모두 지나 끝까지 도달한 뒤에, 다시 출발 지점으로 돌아와야 한다. 전체 코스들을 지나고 있는 상황에서 이동 거리가 K일 때, 현재 지나고 있는 코스의 번호를 출력하는 프로그램을 작성하시오. 단, 이동 거리가 K가 두 코스 사이에 위치한 경우에는 ‘지나야 할’ 코스의 번호를 출력한다. 예를 들어 N=5일 때, 각 코스의 길이가 차례대로 7, 4, 2, 4, 5라고 가정하자. 출발 지점을 0이라고 하면, 전체 코스가 구성된 형태를 다음과 같이 그릴 수 있다. K=0일 때, 1번 코스를 지나고 있으므로 1을 출력한다. K=7일 때, 2번 코스를 지나고 있으므로 2를 출력한다. K=..

백준 16926 - 배열 돌리기1 시간 제한 1초, 메모리 제한 512MB # 조건 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] ↓ ↓ ↑ ↑ A[3][1] A[3][2] → A[3][3] → A[3][4] A[3][5] ↓ ↑ A[4][1] → A[4][2] → A[4][3] → A[4][4] → A[4][5] 예를 들어, 아래와 같은 배열을 2번 회전시키면 다음과 같이 변하게 된다. 1 2 3 4 2 3 4 8 3 4 8 6 5 6 7 8 1 7 7 6 2 7 8 2 ..

백준 22862 - 가장 긴 짝수 연속한 부분 수열(Large) 시간 제한 1초, 메모리 제한 1024MB # 조건 길이가 $N$인 수열 $S$가 있다. 수열 $S$는 1 이상인 정수로 이루어져 있다. 수열 $S$에서 원하는 위치에 있는 수를 골라 최대 $K$번 삭제를 할 수 있다. 예를 들어, 수열 $S$가 다음과 같이 구성되어 있다고 가정하자. 수열 S : 1 2 3 4 5 6 7 8 수열 $S$에서 4번째에 있는 4를 지운다고 하면 아래와 같다. 수열 S : 1 2 3 5 6 7 8 수열 $S$에서 최대 $K$번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 구해보자. 입력 수열 $S$의 길이 $N$와 삭제할 수 있는 최대 횟수인 $K$가 공백으로 구분되어 주어진..

백준 1254 - 팰린드롬 만들기 시간 제한 2초, 메모리 제한 128MB # 조건 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 규완이는 팰린드롬을 엄청나게 좋아한다. 팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다. 동호는 규완이를 위한 깜짝 선물을 준비했다. 동호는 규완이가 적어놓고 간 문자열 S에 0개 이상의 문자를 문자열 뒤에 추가해서 팰린드롬을 만들려고 한다. 동호는 가능하면 가장 짧은 문자열을 만들려고 한다. 동호가 만들 수 있는 가장 짧은 팰린드롬의 길이를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 최대 50이다. 출력 첫째 줄에 동호가 만들 수 있는 가장 짧은 팰린드롬의 길..

백준 1300 - K번째 수 시간 제한 2초, 메모리 제한 128MB # 조건 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B의 인덱스는 1부터 시작한다. 입력 첫째 줄에 배열의 크기 N이 주어진다. N은 10^5보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(10^9, N^2)보다 작거나 같은 자연수이다. 출력 B[k]를 출력한다. # 접근 방법 N의 크기가 100,000까지 가능하므로 모든 좌표의 수를 구하는 것은 메모리 초과가 발생한다. 이 문제의 핵심을 잘 생각해봐야 했는데 K번째 인덱스의 수가 무엇인..