코테 탈출일지

https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 접근 방식 - dp로 푸는 경우, 메모제이션의 활용법 코드 풀이 t = int(input()) for _ in range(t): n, m = map(int, input().split()) dp = [[0]*(m+1) for _ in range(n+1)] # dp[i][j] = 좌에 i개, 우에 j개 스팟이 있을 때의 경우의 수 for i in range(1, n+1): for j in range(..

https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 접근 방식 - 고립된 영역 접근 방식 고민 - 방문 처리 방법 (visited 리스트 or 그래프 직접 표기) 및 시점 - count 시 코드 풀이 from collections import deque m, n, k = map(int, input().split()) # 세로 길이, 가로 길이, 정사각형 수 graph = [[0]*m for _ in range(n)] for _ ..

https://www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 접근 방식 - 특이 조건 (중복 방문 가능) 처리 방식 고민 - 문제 이해 및 함수 선정 코드 풀이 import sys def dfs(node, cnt): # dfs 함수 구현 visited[node-1] = 1 # 방문 처리 for adj in range(1, n+1): # node의 인접 연결 노드 if visited[adj-1] == 0 and graph..

https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 접근 방식 - bfs/dfs 선택 - graph와 visited 리스트의 선언 여부 고민 - 촌수 count 시점 고민 코드 풀이 n = int(input()) graph = [[0]*n for _ in range(n)] # 연결 관계 표현 visited = [0]*n x, y = map(int, input().split()) info = int(input()) for _ in..

https://www.acmicpc.net/problem/1652 1652번: 누울 자리를 찾아라 첫째 줄에 방의 크기 N이 주어진다. N은 1이상 100이하의 정수이다. 그 다음 N줄에 걸쳐 N개의 문자가 들어오는데 '.'은 아무것도 없는 곳을 의미하고, 'X'는 짐이 있는 곳을 의미한다. www.acmicpc.net 접근 방식 - 이중 for문과 인덱싱 방식 고민 - count가 이루어지는 시점 고민 코드 풀이 n = int(input()) room = [] for _ in range(n): tmp = list(input()) room.append(tmp) row = 0 col = 0 for i in range(n): tmpa, tmpb = 0, 0 for j in range(n): if room[i..

https://www.acmicpc.net/problem/2669 2669번: 직사각형 네개의 합집합의 면적 구하기 평면에 네 개의 직사각형이 놓여 있는데 그 밑변은 모두 가로축에 평행하다. 이 네 개의 직사각형들은 서로 떨어져 있을 수도 있고, 겹쳐 있을 수도 있고, 하나가 다른 하나를 포함할 수도 있으 www.acmicpc.net 접근 방식 - 중복 영역에 대한 처리 방식 고민 코드 풀이 grid = [[0]*100 for _ in range(100)] for _ in range(4): a, b, c, d = map(int, input().split()) for i in range(a, c): for j in range(b, d): grid[i-1][j-1] = 1 cnt = 0 # 색칠된 grid ..

https://www.acmicpc.net/problem/1476 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타 www.acmicpc.net 접근 방식 - 변수로 지정할 숫자와 반복문 구상 (연도를 변수로 / 연도에서 e, s, m을 뺀 값을 각각 15, 28, 19로 나눈 몫을 변수로) 코드 풀이 e, s, m = map(int, input().split()) # 1~15, 1~28, 1~19 year = 1 # year = 15x + e = 28y + s = 19z + m while True: # 계속 반복 if (year-e) % 15..

https://www.acmicpc.net/problem/2740 2740번: 행렬 곱셈 첫째 줄에 행렬 A의 크기 N 과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 순서대로 주어진다. 그 다음 줄에는 행렬 B의 크기 M과 K가 주어진다. 이어서 M개의 줄에 행렬 B의 원소 K개 www.acmicpc.net 접근 방식 - 행렬곱 연산의 규칙 구현 코드 풀이 n, m = map(int, input().split()) a = [] for _ in range(n): tmp = list(map(int, input().split())) a.append(tmp) m, k = map(int, input().split()) b = [] for _ in range(m): tmp = list(map(..