Sangmun

https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 파이썬으로 풀면 시간초과가 나는데 pypy로 제출을 하면 통과는 된다... 매번 행렬을 복사하는 것 때문에 그런거 같은데 다른 풀이법을 알아봐야겠다. import sys input = sys.stdin.readline r,c,t = map(int,input().split()) Particulates = [] Particulates_copy = [[0]*c for _ in range(r)] for..

https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net BFS를 이용한 숨바꼭질 문제 시리즈 중에 하나이다. 숨바꼭질 시리즈에서 최단 경로를 구하는 문제의 솔루션을 약간 변형을 하였다. 엣지 케이스를 처리하는 로직을 포함하지 않고 제출을 하지 엣지 케이스 때문에 시간초과가 난다는 문제가 있었다. import sys from collections import deque input = sys.stdin.readline..

https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 기본적인 DP문제이나 메모리 제한이 4메가 밖에 되지 않음으로 무작정 이전의 연산 결과를 저장할 리스트를 만들면 메모리 초과가 나게된다. 이점을 주의를 해서 코딩을 해주면 된다. import sys input = sys.stdin.readline N = int(input()) max_matrix = [0,0,0] min_matrix = [0,0,0] for _ in range(N): a, b, c = map(i..

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 단순히 브루트 포스로 해결이 되는 문제이다... import sys from itertools import combinations input = sys.stdin.readline N, M = map(int,input().split()) matrix = [list(map(int,input().split())) for _ in range(N)] house_position = []..

https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net vertex와 edge의 최대개수가 100개 밖에 되지 않아서 각 vertex에서 시작하는 모든 경우의 수를 브루트 포스로 계산해 주어도 시간초과가 나지 않는 문제이다. 플로이드 와셜과 다익스트라 두개의 방법으로 해결할 수 있다. #dijkstra import heapq import sys input = sys.stdin.readline INF = int(1e9) n,m,r = map(int,input..

https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A = B: result = cnt break if int(str(number) + '1')

https://www.acmicpc.net/problem/1094 1094번: 막대기 지민이는 길이가 64cm인 막대를 가지고 있다. 어느 날, 그는 길이가 Xcm인 막대가 가지고 싶어졌다. 지민이는 원래 가지고 있던 막대를 더 작은 막대로 자른다음에, 풀로 붙여서 길이가 Xcm인 막대 www.acmicpc.net 비트 마스킹으로 풀어도 되는 문제라 가져왔다. 입력 숫자를 이진수로 바꾸었을때 1의 개수를 세주면 정답이 된다. a = bin(int(input())) count = 0 for each in str(a[2:]): if each == '1': count += 1 print(count)

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net def adjacent(x): for i in range(x): if row[x] == row[i] or abs(row[x] - row[i]) == x - i: return False return True def dfs(x): global result if x == N: result += 1 else: for i in range(N): row[x] = i if adjacent(x): dfs(x + 1) N = i..