본문 바로가기

Algorithm/Baekjoon117

1253. 좋다 (Python) 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 풀이 입력으로 주어진 수가 총 몇 개 있는지 딕셔너리를 이용하여 기록한다. 2중 for문을 통해서 모든 수를 더한 경우를 구하고 두 수를 더한 수가 몇 개 있는지를 딕셔너리를 통해서 체크한다. 두 수의 합은 다음과 같이 3가지 경우가 존재한다. 두 수를 합한 값이 두 수와 모두 같은 경우 (ex. 0 + 0 = 0) 이런 경우는 두 수가 모두 0일 때만 존재한다. 0이 좋은 수가 되기 위해서는 리스트에 0이 3개 이상 존재해야 한다. 0, 0 2개만 존재할 경우 두 수를 합한 0이 다른 인.. 2022. 7. 13.
19238. 스타트 택시 (Python) 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 풀이 BFS를 활용한 구현 문제다. 처음에는 현재 택시 위치에서 모든 승객들에 대한 거리를 구해서 최소 힙에 넣어두고 문제에 주어진 조건에 따라서 먼저 태워야 하는 손님을 찾도록 구현했다. 그러다보니 매번 손님과 모든 남은 승객들의 거리를 구해야했고 아마 이 때문에 시간 초과가 발생한 것으로 보인다. 그래서 현재 택시 위치에서 BFS 탐색을 시작하여 가장 먼저 만나게 되는 승객을 찾도록 변경하였다. 위의 그림은 문제에서 주어.. 2022. 7. 13.
12904. A와 B (Python) 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 풀이 문자열 S에 할 수 있는 연산은 다음과 같다. 만약 문자열 S에서 문자열 T를 만들 수 있는지 체크한다면 위의 두 가지 연산을 모두 수행해 봐야 할 것이다. 하지만 반대로 문자열 T에서 문자열 S가 될 수 있는지를 체크하면 현재 문자열 T의 맨 뒤에 문자가 'A'인지 'B'인지에 따라서 한 가지 연산만 하면 된다. 문제에서 주어진 위의 예제를 살펴보자. ABBA를 한 자리의 문자열로 바꾸려면 다음과 같은 작업이 행해진다... 2022. 7. 11.
16724. 피리 부는 사나이 (Python) 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 풀이 dfs를 이용하여 문제를 해결할 수 있다. 방문 체크를 True, False가 아닌 숫자로 기록해준다. 처음 dfs를 할 때는 1을 기록하고 다음 dfs를 할 때는 2를 기록하는 방식으로 방문 체크를 한다. 2를 기록하는 dfs를 하고 있다고 가정해보자. 계속 2를 돌며 dfs를 수행하다가 2를 마주치면 이는 현재 2가 기록된 지점들에 대해서 순환 하고 있다는 뜻이다. 그렇기 때문에 2가 기록된 지점들 중 임의의 지점에 S.. 2022. 7. 11.
2208. 보석 줍기 (Python) 2208번: 보석 줍기 화영이는 고대 유적을 탐사하던 도중 보석을 발견했다. 유적 속에는 N(1 ≤ N ≤ 100,000)개의 보석들이 일렬로 놓여 있었다. 각각의 보석의 가치는 다를 수 있기 때문에, 화영이는 가급적 많은 이득 www.acmicpc.net 풀이 각 보석 가치의 누적합을 구한다. for문을 통해서 M번부터 시작하여 현재 인덱스의 보석까지 주웠다고 가정했을 때 얻을 수 있는 가치의 총 합을 구한다. 보석을 주울 때 최소 M개의 보석을 연속으로 주워야 한다. 문제에서 주어진 예제처럼 M이 4라면 일단 4번째 보석부터 탐색을 시작해야 최소 M개의 보석을 줍는다고 가정할 수 있다. 5번 보석을 마지막으로 주웠다고 가정하면 보석은 1번 또는 2번부터 주워야한다. 5번 보석을 마지막으로 주웠을 때 .. 2022. 7. 6.
14391. 종이 조각 (Python) 14391번: 종이 조각 영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고, www.acmicpc.net 풀이 백트래킹을 통해서 모든 경우의 수를 탐색하면 된다. 자세한건 코드의 주석을 참고하자 코드 # (x, y)에서 (x, ny) 또는 (nx, y)까지 사용된 곳이 있는지를 체크하기 위한 함수 def checkVisited(x, y, nx, ny): for i in range(x, nx + 1): if visited[i][y]: # 이미 사용된 곳이라면 False 반환 return False for i in range(y, ny + 1): if visited[x.. 2022. 7. 6.

티스토리툴바