![]()
문제 & 링크https://www.acmicpc.net/problem/1294 풀이1. 각 문자열을 원하는 대로 쪼갤 수 있기에, 각 문자열(string)의 맨 앞 문자(char) 끼리 비교하여 사전순으로 가장 앞서는 문자 하나를 가져온다.2. 사전순으로 가장 앞서는 문자가 여러 문자열에 있을 경우 그 다음인 두 번째 문자도 고려해야 한다. - 문자열을 쪼개되, 조각의 순서는 유지해야 하는 조건 - 문제의 출력 조건을 만족하기 위해서 뒤의 문자도 고려하여 해당 문자열의 맨 앞 문자 추출 ex) CB, CA이렇게 두 문자열이 있을 경우 맨 앞 문자는 C로 사전순으로 같다. 그러면 두 번째 문자인 A와 B를 비교하여 두 번째 문자열에서 맨 앞 문자를 추출해야 한다. (이 경우 최종 결과 CACB, 만약..
![]()
문제 & 링크https://www.acmicpc.net/problem/13911 풀이1. 음의 가중치가 없는 그래프에서 최단 거리를 구해야 하기에 다익스트라 알고리즘을 사용한다.2. x세권인지 아닌지 판단하는 값이 주어지기에, 다익스트라 알고리즘에서 우선순위 큐에 넣을 때 이 값을 고려한다.3. 모든 집에서 다익스트라를 수행 할 경우 x세권이 아님에도 탐색 대상이 되는 경우가 있기에 비효율적이다.4. 맥도날드 or 스타벅스에서 다익스트라를 수행하여 x세권인 집만 탐색을 한다.5. 모든 맥도날드 or 스타벅스에서 다익스트라를 한 번씩 수행하면, 최악의 경우 9,999개의 노드에 대한 다익스트라 수행으로 시간 초과가 나게 된다. 6. 가상 노드라는 개념을 추가하여 모든 맥도날드의 시작점을 하나로 묶고, 모든..
![]()
문제 & 링크https://www.acmicpc.net/problem/1422 풀이1. K개의 수를 적어도 한 번씩 사용해야 하기에, 모든 수를 이어 붙여서 가장 큰 수를 구하는 문제와 유사하다.2. N > K일 경우 숫자를 중복으로 사용하여 추가할 수 있는데, 자릿수와 값을 생각하면 무조건 K개의 수 중 큰 수를 N - K 만큼 붙여야 한다.3. 숫자를 string으로 바꾸어 사전 순으로 가장 앞서는 수를 구한다. 숫자를 그냥 넣게 될 경우, 아래와 같은 예시가 존재할 수 있다. ex) K = { 31, 34 } -> 사전 순으로 정렬: 34, 31 -> 결과: 3431 (기댓값: 3431) ex) K = { 3, 34 } -> 사전 순으로 정렬: 34, 3 -> 결과: 343 (기댓값: 343) ..
문제 https://www.acmicpc.net/problem/5972문제농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 구두쇠라서 최소한의 소들을 만나면서 지나가고 싶습니다.농부 현서에게는 지도가 있습니다. N (1 다음 지도를 참고하세요. [2]--- / | \ /1 | \ 6 / | \ [1] 0| --[3] \ | / \2 4\ | /4 [6] \ | / /1 [4]..
문제 https://www.acmicpc.net/problem/12840 문제창용이는 여름을 맞이하여 ‘정창용’ 이름이 쓰인 한정판 섬머 에디션 시계를 구입했다. 왠지 오늘은 001도 가고 싶지 않고 시계를 가지고 놀고만 싶다. 우린 방에 있는 창용이가 시계를 가지고 뭘 하는지 궁금하기만 하다. 창용이는 시계의 건전지를 분리했기 때문에 시계는 시간이 흐르지 않는다.창용이는 앞으로 시계를 돌리기도 하고 뒤로 시계를 돌리기도 한다. 입력으로는 초기 현재 시간이 주어지고 q개의 쿼리가 주어진다.한 쿼리는 T로 시작한다. (1 ≤ T ≤ 3, 0 ≤ c ≤ 10,000,000)T가 1일 때는 c를 입력으로 받아와서, 시계를 앞으로 c초 돌린다.T가 2일 때는 c를 입력으로 받아와서, 시계를 뒤로 c초 돌린다.T..
![]()
문제문제디지털시계는 일반적으로 시각을 “hh:mm:ss”의 형태로 표현한다. hh는 00 이상 23 이하의 값을, mm과 ss는 00 이상 59 이하의 값을 가질 수 있다. 이러한 형태의 시각에서 콜론(“:”)을 제거하면 “hhmmss”라는 정수를 얻을 수 있는데, 이러한 정수를 시계 정수라고 한다. 예를 들어, 오후 5시 5분 13초, 즉 17:05:13의 시계 정수는 170513이고, 오전 0시 7분 37초, 즉 00:07:37의 시계 정수는 737이다.이 문제에서 시간이란 시각의 구간을 나타낸다. 예를 들어 [00:59:58, 01:01:24]와 같이 시작하는 시각과 끝나는 시각으로 이루어진 구간을 우리는 시간이라고 부른다. (이러한 구간에는 시작하는 시간과 끝나는 시간도 포함된다)이렇게 시간이 구..
문제문제서쪽나라에서 특수훈련을 받은 정은이는 동쪽나라로 침투를 하게 되었다. 뛰어난 스파이였던 정은이는 동쪽나라의 정보를 입수하게 되었고 정보를 안전하게 서쪽나라로 전달하기 위해 아핀 암호(Affine Cipher)를 이용하기로 하였다.아핀 암호는 다음과 같은 식을 통해 구할 수 있다.E(X) = (aX + b) mod 26A부터 Z까지의 알파벳을 차례대로 0, 1, 2, ... , 25 라고 하자. a = 3이고, b = 1인 경우에 알파벳 A를 아핀 암호식에 대입하면 E(0) = (3 × 0 + 1) mod 26 이 되어 암호화된 결과는 B가 된다.a와 b, 그리고 알파벳 대문자로만 구성된 평문이 주어졌을 때, 이를 암호문으로 치환하는 프로그램을 작성하라.입력입력의 첫 줄에는 테스트 케이스의 개수 T..
6186번: Best Grass그래프 탐색 기본 문제이다.주변 풀들을 한 묶음으로 여기도록 세야한다.import sysinput = sys.stdin.readlinefrom collections import dequedef main(): r, c = map(int,input().split()) arr = [['.' for i in range(c+2)]] for _ in range(r): arr.append(['.']+list(input().strip())+['.']) arr.append(['.' for i in range(c+2)]) visit = [[0 for i in range(c+2)] for j in range(r+2)] ans = 0 def g..
https://www.acmicpc.net/problem/2164 import sysinput = sys.stdin.readline from collections import dequedef main(): n = int(input()) arr = deque([i for i in range(n,0,-1)]) while (1): if len(arr)==1: break arr.pop() x = arr.pop() arr.appendleft(x) print(arr[0])if __name__ == "__main__": main() 생각하지 않고 실제로 돌려봐도 시간 초과 안뜨려나? 했는데 정말 안 떴다. 2초라서 시도해보았다.
![]()
문제 https://www.acmicpc.net/problem/2566입력첫째 줄부터 아홉 번째 줄까지 한 줄에 아홉 개씩 수가 주어진다. 주어지는 수는 100보다 작은 자연수 또는 0이다.출력첫째 줄에 최댓값을 출력하고, 둘째 줄에 최댓값이 위치한 행 번호와 열 번호를 빈칸을 사이에 두고 차례로 출력한다. 최댓값이 두 개 이상인 경우 그 중 한 곳의 위치를 출력한다. Algorithm2차원 리스트상에서 최댓값과 그 인덱스를 찾으라는 문제지만 1차원 리스트에서 더 쉽기에 1차원 리스트로 받는다.1차원 리스트에서 2차원으로 받았을 때의 인덱스를 찾기 위해 1차원 리스트의 인덱스에서 9로 나눈 값과 나머지를 이용한 Codeimport sysfrom operator import indexlst = []fo..
문제 https://www.acmicpc.net/problem/2616문제기차는 맨 앞에 있는 기관차 1대가 손님이 탄 객차 여러 칸을 끌고 간다. 기관차가 고장나면 기차를 운행할 수 없게 되므로 최근 철도청은 기관차 고장에 대비하여 몇몇 역에 소형 기관차 3대를 배치하기로 결정하였다. 소형 기관차는 평소에 이용하는 기관차보다 훨씬 적은 수의 객차만을 끌 수 있다.기관차가 고장났을 때 끌고 가던 객차 모두를 소형 기관차 3대가 나누어 끌 수 없기 때문에, 소형 기관차들이 어떤 객차들을 끌고 가는 것이 좋을까하는 문제를 고민하다가 다음과 같이 하기로 결정하였다.소형 기관차가 최대로 끌 수 있는 객차의 수를 미리 정해 놓고, 그보다 많은 수의 객차를 절대로 끌게 하지 않는다. 3대의 소형 기관차가 최대로 끌..
문제문제그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때문에 그룹 단어이지만, aabbbccb는 b가 떨어져서 나타나기 때문에 그룹 단어가 아니다.단어 N개를 입력으로 받아 그룹 단어의 개수를 출력하는 프로그램을 작성하시오.입력첫째 줄에 단어의 개수 N이 들어온다. N은 100보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 단어가 들어온다. 단어는 알파벳 소문자로만 되어있고 중복되지 않으며, 길이는 최대 100이다.출력첫째 줄에 그룹 단어의 개수를 출력한다.예제 입력 1 복사3happynewyear예제 출력 1 복사3예제 입력 ..
