https://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 문제 문제에 대한 자세한 내용은 백준에서 참고해주세요 풀이 1. 택시 운전자는 가장 가까운 거리에 있는 고객을 먼저 태워야 합니다. (만일 같은 거리에 존재하는 고객이 여러 명이라면 최소 행 위치에 있는 고객을 태우며, 같은 행에 존재하는 고객이 여러 명이라면 최소 열 위치에 있는 고객을 태운다) 이 때 정렬이 필요함을 알 수 있습니다. 2. 택시 운전자의 ..

https://www.acmicpc.net/problem/22352 22352번: 항체 인식 첫 번째 줄에는 SP 촬영 결과의 크기를 의미하는 두 정수 $N$과 $M$이 주어진다. ($1 \le N, M \le 30$) 이는 촬영 결과가 세로로 $N$칸, 가로로 $M$칸 크기의 격자라는 것을 의미한다. 다음 $N$개의 줄에는 www.acmicpc.net 문제 풀이 1. BFS알고리즘을 사용해서 문제를 풀어주기로 했습니다. 2. 우선 완전탐색을 통해서 백신을 놓기 전의 격자와 백신을 놓은 후의 격자를 비교해줍니다. 3. 만일 다른 데이터 값을 가진 격자 위치를 찾게 되면 그 격자 위치를 중심으로 백신을 놓기 전의 격자 위에 백신을 놓은 후의 격자의 데이터 값으로 수정하는 BFS탐색을 진행해줍니다. 4. 만..

https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 문제 풀이 1. 레이저를 뜻하는 ')' 과 쇠막대기의 끝점임을 알리는 ')'의 구분이 필요한 문제여서 flag라는 변수에 직전에 나왔던 문자를 저장해줘서 i 이전에 나온 문자에 따라 레이저인지 쇠막대기인지 구분해주었다. 만일 flag에 '('가 저장되었을 경우에 i가 ')'이면 레이저를 뜻하고, flag에 ')'가 저장되었을 경우에 i가 ')'이면 쇠막대기의 끝점을 뜻한다. 2. 쇠막대기의 끝점이 등장하면 ..

https://www.acmicpc.net/problem/28278 28278번: 스택 2 첫째 줄에 명령의 수 N이 주어진다. (1 ≤ N ≤ 1,000,000) 둘째 줄부터 N개 줄에 명령이 하나씩 주어진다. 출력을 요구하는 명령은 하나 이상 주어진다. www.acmicpc.net 문제 풀이 간단한 스택 구현 문제입니다. 조건문에 신경써서 문제를 풀어주세요. 코드 # 28278번 스택 2 import sys st = [] t = int(input()) for _ in range(t): order = sys.stdin.readline().rstrip().split() if len(order) == 2: st.append(order[1]) else: if order[0] == "2": if st: pri..

https://www.acmicpc.net/problem/3986 3986번: 좋은 단어 이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 www.acmicpc.net 문제 풀이 1. 좋은 단어라는 것이 무엇인지 처음에 파악하는게 중요하다고 생각했습니다. 좋은 단어는 다음과 같이 아치형 곡선을 그렸을 경우. 겹치지 않고 모두 짝을 이뤄야 합니다. 따라서 좋은 단어는 AABB, ABBA와 같은 글자들입니다. 2. 규칙을 파악해보니 좋은 단어의 조건은 다음과 같습니다. 1. A, B의 각 글자 수가 짝수여야합니다. 2. 아치형 곡선이 겹치는 경우는 짝을 이뤄주지 못하는 글자가..

https://www.acmicpc.net/problem/5397 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입 www.acmicpc.net 문제 풀이 처음에는 리스트 한 개와 인덱스를 이용해서 커서의 위치를 구현해주려 했으나 커서를 기준으로 오른쪽과 왼쪽의 문자를 알려주는 두 개의 리스트를 사용하면 훨씬 쉽게 구현할 수 있다는 것을 알게 되었습니다. [커서 기준 왼쪽 문자들] 커서 [커서 기준 오른쪽 문자들] 이렇게 구현하면 훨씬 쉽게 구현할 수 있다. 정답을 출력할 때 오른쪽 문자들은 마지막에 한번 뒤집어줘야한다. appen..

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 문제 풀이 한칸 당 독립적인 국가라고 생각하면 됩니다. 이동 가능한 경로를 dxys 튜플을 통해 정의하고, 너비 우선 탐색(BFS)를 통해서 연합이 될 수 있는 국가인지 확인하기로 했습니다. 여기서 연합이 될 수 있는 조건은 두 국가의 인구 차이가 L 이상 R 이하이면 조건을 만족합니다. visited 배열을 boolean으로 관리하여, 해당 국가를 방문했는지 여부를 체크합니다. 인..

문제 https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 풀이 문제를 풀기 위해서 다음과 같은 점화식이 필요하다. 주어진 화폐 단위 별로 해당하는 금액을 완성할 수 있는 동전을 구성하는 개수를 찾아준다. 1. dp[0]을 1로 초기화합니다. 이는 금액 0을 만드는 방법이 하나밖에 없음을 의미합니다(아무 동전도 사용하지 않는 경우). 2. 모든 동전 단위 coin[i]에 대해 반복합니다. 3. 각 coin[i]에 대해 금액 coin[..