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

백준 14442 - 벽 부수고 이동하기2 시간 제한 2초, 메모리 제한 512MB # 조건 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단 경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 K개 까지 부수고 이동하여도 된다. 한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다. 맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오. 입력 첫째 줄에 N(1 ≤ N ≤..

백준 11660_구간 합 구하기5 조건 NxN 개의 수가 NxN 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램 작성하시오 입력 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다. 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 ≤ x2, y1 ≤ y2) # 접근 방법 단순 슬라이싱을 통해 풀면 시간초과가 발생한다. 현재 좌표를 (0,0)에서 시작한 사각형의 ..

백준 14400 - 편의점2 시간 제한 2초, 메모리 제한 512MB # 조건 영선이는 이번에 편의점으로 창업을 하려고 계획 중이다. 이번 창업을 위해 많은 준비를 하고 있는데, 아직 편의점을 세울 위치를 결정을 하지 못했다. 영선이는 미리 시장조사를 하여, 주요 고객들이 어느 위치에 존재하는지 파악을 하였고, 모든 고객들의 거리의 합을 최소로 하려한다. 두 위치의 거리는 |x1-x2|+|y1-y2|로 정의한다. n명의 주요 고객들의 위치 (xi,yi)이 주어질 때, 모든 고객들의 거리 합을 최소로 하는 위치에 편의점을 세울 때, 그 최소 거리 합을 출력하시오. 입력 첫째 줄에는 주요 고객들의 수n이 주어진다.(1≤n≤100,000) 다음 n줄에는 고객들의 위치 (x,y)가 주어진다.(-1,000,000..

백준 14889 - 스타트와 링크 시간 제한 2초, 메모리 제한 512MB # 조건 오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다. BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij..

백준 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$가 공백으로 구분되어 주어진..

백준 1463_1로 만들기 조건 X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다 위 3개의 연산을 적절히 사용해서 1을 만들어 주자. 접근 방법 최소의 연산을 구하는 문제이다. 2 또는 3으로 나누어 떨어지지 않는 경우 무조건 1을 빼야한다. 이후는 2와 3으로 나누어주면 되는데 min을 통하여 빼주는 것과 나누어주는 것의 최소값을 구해준다. n=>1이 아닌 1 => n의 형식으로 dp 인덱스 => 연산 값, dp의 값 => 연산 횟수로 이용해준다. n = int(input()) dp = [0] * (n+1) for i in range(2, n+1): # 나눠지지 않는다면 무조건 1씩 빼야하므로 연산횟수 +1 dp[i] = dp[i-1] + 1 # 나누..

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