문제 https://www.acmicpc.net/problem/1789 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net 풀이 S의 값을 만들 수 있는 서로 다른 수 N을 구하는 문제 먼저 1부터 N까지의 합을 구해야 하기 때문에 공식을 사용한다. 1부터 n까지의 합 : (n * (n + 1)) / 2 위 공식을 적용했을 때 해당 값이 S를 넘어갔다면 새로 들어온 값을 포함하고, 기존에 있던 값을 빼면 S를 만들 수 있으므로 N-1개의 서로 다른 수로 만들 수 있음을 알 수 있다. ex) S = 11, n_arr = [1, 2, 3, 4, "5"]이다. 그렇다면 n_arr에서 4를 제거하면 n_arr = [1, 2, 3, 5]이..
문제 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 풀이 적절한 집의 위치에 공유기를 C개 설치하고 가장 인접한 부분의 최댓값을 구하는 문제 이 문제를 해결하기 위해서는 이분 탐색을 이용해야 하는데, 인덱스 값이 아닌 숫자 값으로 구해야 한다. 이분 탐색 수행시 cnt가 더해지는 조건은 현재의 위치(data[i])가 최근 위치와 mid((start + end) // 2)의 합보다 크거나 같은..
문제 https://www.acmicpc.net/problem/9944 9944번: NxM 보드 완주하기 N×M 보드 위에서 할 수 있는 게임이 있다. 보드는 크기가 1×1인 정사각형 칸으로 나누어져 있다. 보드의 각 칸은 빈 칸 또는 장애물이다. 장애물은 아래 그림에선 어두운 사각형으로 표시되어져 www.acmicpc.net 풀이 구현하는 문제는 사실하라는 대로만 하면 문제를 해결할 수 있지만, 자세한 부분에서 문제가 발생하기 마련이므로 조건에 대한 정확한 정의가 필요하다. 아래에 이 문제를 해결할 때 고려해 볼 법한 사항을 작성해 보았다. 보드 위에 공을 두고 벽이 아닌 모든 칸을 방문할 수 있다면 이동한 경우의 최솟값으로 정답을 출력하고, 그렇지 못한다면 -1을 출력한다. 종료하는 조건이 따로 없으..
문제 https://www.acmicpc.net/problem/1063 1063번: 킹 8*8크기의 체스판에 왕이 하나 있다. 킹의 현재 위치가 주어진다. 체스판에서 말의 위치는 다음과 같이 주어진다. 알파벳 하나와 숫자 하나로 이루어져 있는데, 알파벳은 열을 상징하고, 숫자는 www.acmicpc.net 풀이 움직이는 방향이 주어지고 그에 맞게 킹과 돌을 움직이는 문제 문제를 해결하려면 아래 두가지 경우를 고려해야 한다. 킹을 움직였는데 범위 밖인 경우 킹을 범위 내에서 움직이고, 그 자리에 돌이 있어 돌도 같은 방향으로 움직였을 때 범위 밖인 경우 위의 두 가지 경우를 잘 고려한다면 문제를 해결할 수 있다. 제출 코드 # 2023/02/21 구현 # https://www.acmicpc.net/prob..
문제 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..
