문제 https://www.acmicpc.net/problem/9657 9657번: 돌 게임 3 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 풀이 DP를 이용해 언제 돌을 두는지 확인한다. 만약 해당 칸이 1인 경우는 상근이가 둔 곳이고, 해당 칸이 0인 경우는 창영이가 둔 칸이다. 1 0 1 1인 경우 5번째에는 N(5) - 3 번째 칸이 0이므로 돌을 가져갈 수 있다. 그러므로 1 0 1 1 1이 된다. 이런 식으로 현재 구역에 0이 들어가는지, 1이 들어가는지를 정의할 수 있다면, 정답을 구할 수 있다. 제출 코드 # 2023/02/20 DP # https://www.acmicpc.net/problem/9657 N = int(input()) ..
문제 https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 풀이 각 방향에 맞는 구역을 탐색하게 해 보고 사각지대의 값이 가장 작은 구성을 만든 후 정답을 출력하는 문제 이론은 간단하나 구현하기가 많이 어려웠던 문제이다. cctv의 정보를 배열에 담고, 해당 번호에 맞는 탐색 방법을 선택한다. 그런 후 최적의 회전 방법을 찾은 다음, cctv 위치의 방문 여부와 벽의 개수 적절히 계산해서 사각지대의 값을 구하면 된다. cctv가 감시를 시..
문제 https://www.acmicpc.net/problem/8980 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net 풀이 중요한 건 도착한 지점의 값이므로 해당 값을 기준으로 배열을 정렬한다. 먼저 도착 지점에 도달하기 전까지 최대로 들 수 있는 박스의 개수를 구한다. 현재 들고 있는 박스의 값과 비교한다. 도착 지점에 도착할 때까지 그 값을 빼준다. (해당 박스의 개수만큼 들고 도착 지점까지 가야 할 것이기 때문이다.) 제출 코드 # 2023/02/16 Greedy # https://..
문제 https://www.acmicpc.net/problem/20044 20044번: Project Teams 입력은 표준입력을 사용한다. 입력의 첫 번째 행에는 팀 수를 나타내는 양의 정수 n(1 ≤ n ≤ 5,000)이 주어진다. 그 다음 행에 학생 si 의 코딩 역량 w(si)를 나타내는 2n개의 양의 정수가 공백으로 www.acmicpc.net 풀이 팀을 균형에 맞게 구성해야 하는 문제 먼저 역량을 담은 배열을 정렬한 다음, 양 끝의 사람들끼리 팀을 이룬다면 역량에 맞게 구성할 수 있다. 제출 코드 # 2023/02/15 Greedy # https://www.acmicpc.net/problem/20044 import sys input = sys.stdin.readline N = int(input..
대회 링크 https://codeforces.com/contest/1792 A. GamingForces https://codeforces.com/contest/1792/problem/A 문제 풀이 2 개체의 체력을 각각 1씩 감소하는 방법과 하나의 체력을 전부 감소시키는 방법을 통해 모든 개체의 체력이 0이 된다고 할 때, 그 최소 횟수를 출력하는 문제 현재 대상의 값을 구하고 만약 그 값이 1보다 크다면 1 개체를 선택에서 없애는 것이 더 좋은 방법이다. 따라서 0인 경우는 넘기고, 1인 경우는 각각 감소시키고(배열안에 값이 있는 경우), 그 이상인 경우는 하나를 선택해 0으로 만든다. 제출 코드 # 2023/02/15 Greedy # https://codeforces.com/contest/1792/p..
문제 https://www.acmicpc.net/problem/2885 2885번: 초콜릿 식사 학교 근처 편의점에 새 초콜릿이 들어왔다. 이 초콜릿은 막대 모양이고, 각 막대는 정사각형 N개로 이루어져 있다. 초콜릿의 크기(정사각형의 개수)는 항상 2의 제곱 형태이다. 즉, 1, 2, 4, 8, 16, ... www.acmicpc.net 풀이 초콜릿 나누기 문제 K 만큼의 초콜릿 조각을 만들려면 K 보다 큰 2^n의 크기의 초콜릿이여야 한다. 만약 나누어지면 정답을 출력한다. 그리디 문제는 쉽게 보여도 많이 어렵다. 제출 코드 # 2023/02/14 그리디 # https://www.acmicpc.net/problem/2885 K = int(input()) two = [] p = 1 # 초콜릿 크기는 K..
문제 https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 풀이 목적지까지 도달할 때 사용 하는 거울의 최소 값을 출력하는 문제 맨 처음 풀었을 땐 단순히 한쪽 방향으로 계속 진행시키고 만약 도달한 경우 정답을 출력하는 방법으로 문제를 해결했었다. 재채점 이후 시간초과가 발생했는데 그 이유는 중복방문 때문이었다. 따라서 해당 문제를 해결하기 위해 방문 기록을 들어온 방향에 따라 저장할 수 있도록 구현해서 문제를 해결했다. 제출 코드 1(시간..
문제 https://www.acmicpc.net/problem/27453 27453번: 귀엽기만 한 게 아닌 한별 양 첫 번째 줄에 마을의 세로 크기 $N$, 가로 크기 $M$, 한별이가 연속해서 막을 수 있는 불상사의 개수 $K$가 주어진다. ($2\leq N,M\leq 1\,000$, $0\leq K\leq 27$) 다음 $N$ 개의 줄에 걸쳐 마을의 상태가 주어진 www.acmicpc.net 풀이 지나온 3칸의 불상사 합과 이전에 들렀던 칸은 이동할 수 없다는 것을 생각해서 구현해야 하는 문제 갈 수 없는 곳의 조건 설정을 잘해야 한다. 내가 설정한 갈 수 있는 조건은 다음과 같다. 벽("X")이 아닌 경우 이전에 방문했던 곳(item)이 아닌 경우 방문하지 않았거나(-1) 해당 구역의 불상사가 다..
