링크: https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 아이디어 백트래킹을 통해 수열 구함 방문처리로 본인은 다시 선택하지 못하게 함 remember 변수로 중복되는 수열이 나오지 않도록 구현 구현 import sys input = sys.stdin.readline def dfs(): if len(temp) == m: print(*temp) return remember = 0 for i in range(n): if not visited[i] ..
링크: https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 아이디어 첫 미세먼지의 좌표와 공기 청정기의 좌표를 미리 저장해 둔다. bfs에서 상요한 큐를 이용해 미세먼지를 확산시킨다. 확산된 배열을 복사해서 저장 공기청정기를 작동 위아래 별개로 구현 원하는 만큼 반복은 bfs인자로 t를 넘겨 한 번 확산 청정을 실행할 때마다 -1 t가 0이 되면 미세먼지의 양을 sum을 통해 구해 출력 구현(메모리, 시간 모두 최악) import sys inpu..
링크: https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 아이디어 bfs로 탐색을 시작 +1과 -1은 cnt를 증가시키고 *2는 그냥 위치만 이동 *를 할 때 0이 되면 무시 (무한반복방지) k에 도착했을 때 k의 cnt 출력 구현(99% 실패) from collections import deque def bfs(N): visited = [0] * 100001 q = deque() q.append(n) whi..
링크: https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 아이디어 백트래킹으로 case배열에 li 에 있는 요소를 넣을 수 있는 모든 경우를 구함 case의 크기가 m과 같아지면 case를 출력해준다 넣을떄 이미 case에 있는 요소는 넣지 말아라 구현 import sys input = sys.stdin.readline def back(): if len(case) == m: for i in case: print(i, end=" ") pr..
링크: https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 아이디어 case가 빨 초 파 3개뿐이니 3가지 경우의 처리만 해주면 될 듯 dp테이블을 만들고 첫 시작은 li와 같게 설정하고 dp[i][j] = min(dp[i-1][중복되지 않는 경우], dp[i-1][중복되지 않는 경우])+li[i][j] 이런 식의 점화식을 사용 2중 for문을 돌며 dp 테이블을 다 채우고 dp배열의 마지막 요소의 min() 값을 출력하면 될..
링크: https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 아이디어 f - 총 층수 s - 현재 층 g - 스타트링크의 층 u - 위로 u칸 가는 버튼 d - 아래로 d칸 가는 버튼 bfs로 위와 아래로 가는 경우로 나눠 그래프를 그린다. 방문처리와 깊이를 동시에 판별하는 배열을 사용 g에 방문처리가 됐으면 방문처리 배열의 값을 반환 구현(틀림) import sys input = sys.stdin.readline # f - 총 층수 # s - 현재 층 # g ..
링크: https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 아이디어 그냥 백트래킹으로 2명을 뽑는 경우 2가지를 만들고 만들어졌을 때 스타트와 링크의 전력차이를 구하여 최소값과 비교하며 저장하면 될듯? 구현(틀림) import sys input=sys.stdin.readline def back(): global minv if len(tmp) == 2: start = li[tmp[0][0]][tmp[0][1]] + li[tmp[0][1]][tmp[0][0]] link =..
링크: https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱 www.acmicpc.net 아이디어 부호의 개수만큼 부호가 들어있는 배열 생성 그 배열의 수열의 경우의 수를 구하는 백트래킹 생성 경우가 만들어지면 계산하여 리스트에 저장 리스트에서 최대 최소값을 출력 구현 (시간초과) import sys input = sys.stdin.readline # 부호가 올 수 있는 모든 경우의 수 백트래킹 def back(): i..
