백준

[백준] 2143. 두 배열의 합 - 파이썬

[Gold III] https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 풀이 부 배열의 합.. -> Prefix Sum! 우선 prefix sum을 구현하기 위해.. Sk (1~k번째 합)를 저장할 배열을 각각 생성. 그 다음이 문제인데... 우선 배열의 원소 조건이 절댓값이 1,000,000을 넘지 않는 정수 이기 때문에.. A[k+1] >= A[k] 가 아니다. 따..

[백준] 17142. 연구소 3 - 파이썬

[Gold III] https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 이 문제는... 사실 토마토나, 백조의 호수 같은 문제와 유사한 문제였으나, 시간이 조금 걸렸다. 문제를 푸는 핵심은, '비활성화된 바이러스 또한 전염이 진행될 수 있도록 처리할 것.' 그리고, '비활성화된 바이러스가 활성화되는 것은 최소 시간을 측정하는 데에 고려하지 않아야 할 것.' 이것들을 유념하며 문제를 풀어 나가야 한다. 풀이 1 일단 BFS 문제라..

[백준] 16173. 점프왕 쩰리 (Small) - 파이썬

[Silver IV] https://www.acmicpc.net/problem/16173 16173번: 점프왕 쩰리 (Small) 쩰리는 맨 왼쪽 위의 칸에서 출발해 (행, 열)로 나타낸 좌표계로, (1, 1) -> (2, 1) -> (3, 1) -> (3, 3)으로 이동해 게임에서 승리할 수 있다. www.acmicpc.net 풀이 N = int(input()) q = [] board = [] for _ in range(N): board.append(list(map(int, input().split()))) q.append([0, 0]) while q: row, col = q.pop() a = board[row][col] if a == -1: print("HaruHaru") exit() if a == ..

[백준] 9095. 1, 2, 3 더하기 - 파이썬

[Silver III] https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 풀이 간단한 Dynamic Programming 문제. n이 11보다 작다 는 조건이 걸려 있어, Top-Down 방식으로 재귀를 이용해 풀어도 시간초과나, Recursion 기본 횟수(1000회) 제한에 걸리지 않을 법 한 문제였다. [정수 k를 1, 2, 3의 합으로 나타내는 방법의 수] = [k-1을 나타내는 방법의 수] + [k-2을 나타내는 방법의 수] + [k-3을 나타내는 방법의 수] 라는 것만 캐치한다면, Bottom-Up 방식으로 Memoization 하며..

[백준] 1987. 알파벳 - python

[Gold IV] https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 풀이 1 이건 그냥.. DFS, Backtracking 이용해서 Recursion으로 풀면 되겠다- 라고 간단하게 생각했다. 그런데 가볍게 짠 코드에서 TLE. import sys sys.setrecursionlimit(100000) R, C = map(int, input().split()) board = [list(input()) for _ in range(R)] res..

[백준] 1647. 도시 분할 계획 - python

[Gold IV] https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 풀이 문제를 딱 보고서 생각한 것 -> Minimum Spanning Tree구나. MST를 구현하고 나서, 남은 edge들 중 가장 value가 높은 것을 제거하면 될 것 같다. line 13의 = 를 ==로 오타내서 찾는데 시간 좀 씀...ㅎ 아무튼 clear. from collections import deque N, M = map(in..

[백준] 12100. 2048 (Easy) - 파이썬

[Gold II] https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 풀이 유명한 2048 게임을 구현하는 문제였다.. 일단 보드의 크기도 최대 1 0: row[j] = row[j-1] j -= 1 row[0] = 0 temp = 0 # 합쳐져서 한 칸 당겼다면 다시 그 index부터 검사 index += 1 else: temp = row[index] index -= 1 return board def up(board):..

[백준] 11049. 행렬 곱셈 순서 - 파이썬

[Gold III] https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 풀이 [백준] 10942. 팰린드롬? - 파이썬 [백준] 9252. LCS 2 - 파이썬 [백준] 7579. 앱 - 파이썬 최근 풀었던 위 3개의 DP 문제와 크게 다를 것이 없었던 문제. 근데 DP는 DP인 걸 알아도.. 문제마다 다른 상황에 맞춰서 풀이를 생각해내기 쉽진 않음. 그리고 Line 28의 i += 1 이거 하나 빼먹어서 30분동안 찾았다.........