Python

19235 모노미노도미노

문제 https://www.acmicpc.net/problem/19235 19235번: 모노미노도미노 모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, www.acmicpc.net 접근 문제에 주어진 대로 구현하면 되는 시뮬레이션 문제 어떻게 풀어야 간단할까?? 초록색 보드와 파란색 보드에 대한 처리를 함수 하나로 구현하면 편하기 때문에 파란색 보드를 시계방향으로 90도회전시켜서 생각한다. 풀이 1. 블록 처리 1번 블록: 초록색 보드와 파란색 보드 모두 1번 블록으로 처리 2번 블록: 초록색 보드는 2번 블록으로 파란색 보드는 3번 블록으로 처리 3번 블록: ..

16960 스위치와 램프

문제 https://www.acmicpc.net/problem/16960 16960번: 스위치와 램프 첫째 줄에 스위치의 수 N, 램프의 수 M이 주어진다. 둘째 줄부터 N개의 줄에는 스위치에 대한 정보가 주어진다. 스위치 정보의 첫 번째 정수는 그 스위치와 연결된 램프의 수이고, 이후 연결된 램 www.acmicpc.net 접근 N개의 스위치마다 해당 스위치를 누르지 않았을 때 M개의 모든 램프를 켤 수 있는지 확인한다. 한 스위치에 M개의 램프가 연결된 경우에는 항상 N-1개의 스위치로 모든 램프를 켤 수 있기 때문에, 실제 시간 복잡도는 이론상 계산한 O(N^2 * M) 보다 훨씬 작을 것이다. 풀이 각 스위치에 연결된 램프를 저장하기 위해 딕셔너리 사용 각 스위치를 누르지 않았을 때 N-1개의 스..

1781 컵라면

문제 https://www.acmicpc.net/problem/1781 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net 접근1 (틀림) 가장 먼저 생각한 방법은 딕셔너리를 사용해서 데드라인 별로 얻을 수 있는 컵라면을 리스트 형태로 저장한 후 정렬해서 각 데드라인 일자마다 문제 풀이가 가능한 갯수만큼 더하는 방법으로 작성 But, 많은 컵라면을 얻을 수 있는 문제의 데드라인 값이 큰 경우, 해당 문제를 풀기 전 데드라인 값이 작은 문제들을 먼저 풀어버려서 많은 컵라면을 얻을 수 있는 문제는 못 풀게될 가능성) 접근2 ..

17175 피보나치는 지겨웡~

문제 https://www.acmicpc.net/problem/17175 17175번: 피보나치는 지겨웡~ 혁진이는 알고리즘 문제를 만들라는 독촉을 받아 스트레스다. 하지만 피보나치 문제는 너무 많이 봐서 지겹기 그지없다. 그러나 문제를 만들 시간이 없는 혁진이는 피보나치 문제를 응용해서 www.acmicpc.net 접근 출력을 1000000007로 나눈 나머지로 하라는 것은 피보나치 함수 호출의 숫자가 1억보다 큰값이 존재한다는 뜻이므로, 실제로 피보나치 함수를 구현해서 호출 횟수를 세는 방법은 시간초과가 난다. (제한시간 1초) 어떠한 값 i에 대한 피보나치 함수 호출 횟수는 i-1의 피보나치 함수 호출 횟수와 i-2의 피보나치 함수 호출 횟수의 합이므로 다이나믹 프로그래밍으로 접근 풀이 dp[i]를..

15918 랭퍼든 수열쟁이야!!

문제 https://www.acmicpc.net/problem/15918 15918번: 랭퍼든 수열쟁이야!! 세 자연수 n, x, y가 주어진다. (2 ≤ n ≤ 12, 1 ≤ x < y ≤ 2n, 1 ≤ y-x-1 ≤ n) www.acmicpc.net 접근 비슷한 문제를 풀었던 적이 있어서 바로 백트래킹으로 접근 풀이 먼저 x와 y 사이에 숫자가 몇개(diff) 들어가는지 계산해서, 결과 배열의 x번째와 y번째를 diff로 채우고 시작 결과 배열의 idx를 기준으로 1부터 n까지의 숫자 중 이전에 사용하지 않았던 숫자(i)에 대해 idx번째와 idx+i+1번째에 해당 숫자를 집어넣을 수 있는지 확인하고, 집어넣을 수 있으면 결과 배열에 숫자를 채우고 idx+1로 넘어간다. 만약 해당 idx번째에 이미 ..

11411 합 구하기

문제 https://www.acmicpc.net/problem/11441 11441번: 합 구하기 첫째 줄에 수의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄에는 A1, A2, ..., AN이 주어진다. (-1,000 ≤ Ai ≤ 1,000) 셋째 줄에는 구간의 개수 M이 주어진다. (1 ≤ M ≤ 100,000) 넷째 줄부터 M개의 줄에는 www.acmicpc.net 접근 주어진 수의 개수 n과 구간의 수 m의 범위가 1

13702 이상한 술집

문제 https://www.acmicpc.net/problem/13702 13702번: 이상한 술집 프로그래밍 대회 전날, 은상과 친구들은 이상한 술집에 모였다. 이 술집에서 막걸리를 시키면 주전자의 용량은 똑같았으나 안에 들어 있는 막걸리 용량은 랜덤이다. 즉 한 번 주문에 막걸리 용 www.acmicpc.net 접근 막걸리 주전자의 개수(s개)가 나누어줄 사람(c개)보다 작거나 같고, 정해진 용량을 나누어주고 남은 막걸리는 버린다고 했으므로, 나누어줄 수 있는 막걸리의 최댓값을 결정할 수 있다. 0과 최댓값 사이에서 문제의 제한조건을 만족시키는 경우를 찾아 나서면 되므로, 이분탐색으로 풀이 풀이 lt를 1로, rt를 주전자에 들어있는 막걸리의 최솟값으로 설정 mid 값에 대해서 각 주전자마다 몇 명에..

2110 공유기 설치

문제 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 접근 주어진 집들(n개)에 공유기(c개)를 설치할 때, 가장 인접한 두 공유기 사이의 최대 거리를 구하는 문제 가장 처음 든 생각은 집들 중 공유기를 설치할 집들을 선택하는 방법으로 접근하려 했으나, 이 방법의 시간 복잡도는 nCc이며, n과 c의 범위가 2 ≤ n ≤ 200,000, 2 ≤ c ≤ n 이므로 시간초과가 날 것 (제한시간 2..