CEO

문제 2003번: 수들의 합 2 첫째 줄에 N(1≤N≤10,000), M(1≤M≤300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 문제 풀이 N 크기의 수열이 주어질 때, 수열의 부분 합 중 M을 만족하는 개수를 반환하는 문제이다. 문제를 효율적으로 풀기 위해서는 미리 1 ~ N까지의 누적합을 계산한 후에 시작, 끝 지점을 달리하며 부분합을 계산하면 된다. 예제 입력 1을 기준으로 합을 누적시키면 [0, 1, 2, 3, 4]와 같이 합이 누적된다. 이를 시작 끝 지점을 0, 1로 두고 조건에 따라 순차적으로 증가시켜 가며 탐색을 하면, 전체 부분합에 대한 경..

문제 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 N까지 숫자 중 K개를 이용해서 N이 되는 경우의 수를 구하는 문제이다. 어떤 방식으로 풀면 좋을지 고민하다가, 단순히 N이 1인 경우부터 시작해서 K가 증가할 경우 경우의 수를 찾아보았다. N이 1인 경우 K에 따라 발생하는 경우의 수 1 : [1] → 1가지 2 : [0 + 1], [1 + 0] → 2가지 3 : [0 + 0 + 1], [0 + 1 + 0], [1 + 0 + 0] → 3가지 4 : 4가지 N이 2인 경우 K에 따라 발생하는 경우의 수 1 : [2] → 1가지 2 : [0 + 2], [1 + 1], [2 + 0] → 3가지 3 : [0 + 0 + 2], ..

문제 3055번: 탈출 문제 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치�� www.acmicpc.net 문제 풀이 고슴도치(S)가 비버의 굴(D)로 탈출 할 수 있는지를 찾는 문제이다. 다른 그래프 문제와 다른 점은 시간에 따라 물(*)이 비어 있는 칸으로 확장하는 것이다. 가만히 들여다 보면 어려운 문제는 아니고, 다음과 같은 처리가 필요하다는 것을 알 수 있다. 시간에 따라 물이 확장하는 경우 물이 확장 하는 것은 토마토의 로직과 같이 구현하면 물이 퍼지는 상황을 구현 할 수 있다. 고슴 도치가 비버 굴로 가기 위한 방법 다른 그래프 문제와 마찬가지로 BFS를 통..

문제 15644번: 구슬 탈출 3 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 문제 풀이 앞서 다룬 문제인 구슬 탈출을 이해하고 있다면, 쉽게 풀 수 있는 문제이다. 이전의 문제와 다른 점이 있다면 구슬 탈출 2의 문제에서 이동 경로도 함께 출력하는 것이다. visited의 경우 단순히 방문 여부를 체크하는 False / True 형태로 선언할 수도 있지만, visited를 문자로 선언하게 되면 각 방문에 따라 방문 경로를 확인할 수 있다. dirs = {'R': (0, 1), 'L':..

문제 13459번: 구슬 탈출 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 문제 풀이 기존의 그래프 문제들은 상, 하, 좌, 우로 탐색하여 하나의 목표에 대해 이동 가능한지 판단하는 문제들이었다. 하지만 이 문제는 2개의 구슬들이 기울기에 따라 상, 하, 좌, 우로 동시에 이동하는 경우에 빨간 구슬부터 먼저 탈출 가능한지를 판단하는 문제이다. 또한, 시도 횟수 10회를 초과하지 않고 탈출할 수 있어야 한다. 다른 그래프 문제들은 한 번에 한 칸씩 상, 하, 좌, 우로 이동 가능한지 파악..

문제 1987번: 알파벳 문제 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 www.acmicpc.net 문제 풀이 그래프를 상, 하, 좌, 우로 탐색하는데 알파벳이 중복되지 않는 한 이동할 수 있다. 이때 최대로 이동할 수 있는 거리를 계산하여 반환하는 문제이다. 처음에는 각 경우에 대해 모두 탐색하여야 한다고 생각하여 백트랙킹을 생각하로 DFS로 작성하였는데, 파이썬으로는 통과할 수 없었다. 따라서 BFS로 풀었는데 BFS 역시 `deque`를 사용하니 메모리 초과가 발생하여 문제를 풀 수 없었다. 다른 사람들의 풀이를 참고하니, 큐 안에 중복되는 ..

문제 16198번: 에너지 모으기 N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다. i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있� www.acmicpc.net 문제 풀이 문제는 구슬들 중에 특정 구슬을 제거하고, 제거한 구슬 주위의 값들을 곱하는 방식을 통해 구슬이 2개가 될 때까지 계속해서 진행하여 제거하는 경우에 따라 가장 큰 값을 가지는 경우를 반환하는 문제이다. 문제에서 발생할 수 있는 경우의 수는 위의 그림과 같이 생각할 수 있다. 그림은 예제 입력 1에서 발생할 수 있는 경우의 수를 나타낸 경우이다. 구슬이 4개 이므로 발생할 수 있는 경우의 수는 2가지가 된다. 그림에서 알 수 있듯이 어떤 구슬..

문제 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 문제 풀이 가로, 세로와 3 X 3 영역을 확인하여 스도쿠 퍼즐에 채워지지 않은 숫자 중 알맞은 숫자를 채우는 문제이다. 채워지지 않는 곳은 0으로 제시된다. 따라서 0인 부분의 좌표를 찾고 해당 좌표에 어떤 값을 대입하면 되는지 확인하면 된다. 확인하는 방법은 다음과 같다. 한 행에 어떤 값이 없는지 확인한다. 한 열에 어떤 값이 없는지 확인한다. 그래프의 행/열을 전환시켜 확인하면 쉽다. 3 X 3 영역에 어떤 값이 없는지 확인한다. 코드 from sy..