시나위

https://www.acmicpc.net/problem/16507 16507번: 어두운 건 무서워 첫 번째 줄에는 사진의 크기를 의미하는 정수 R, C (1 ≤ R, C ≤ 1,000)와 사진 일부분의 밝기 평균을 알아볼 개수를 의미하는 정수 Q (1 ≤ Q ≤ 10,000)가 주어진다. 다음 R개의 줄에 걸쳐 R×C 크기의 사 www.acmicpc.net 이차원 배열을 사용한 누적합 문제이다 밝기의 평균을 구할때마다 항상 더하고 나누는 연산을 하는건 꽤 오래 걸린다. 그래서 누적합을 구한다음 특정 범위에서의 합을 구하고 해당 범위의 넓이로 나누면 된다. 일차원 배열에선 누적합을 구할땐 이전 인덱스 값만 계속 더해주면 되는데, 이차원 배열에서 누적합을 구할 땐 행과 열에서 이전 인덱스(memo[i-1]..

https://www.acmicpc.net/problem/14467 14467번: 소가 길을 건너간 이유 1 3번 소는 위치 1, 0, 1에서 관찰되었으므로 길을 최소 두 번 건넜음을 확인할 수 있다. 4번 소도 길을 한 번 건넜으며, 나머지 소는 길을 건넌 기록이 확인되지 않는다. www.acmicpc.net 오늘은 쉬운 문제 하나만... 값이 없으면 추가하고, 있으면 들어있는 값과 비교해서 다른 경우에 길을 건너갔다고 체크하면된다. # import sys; input = sys.stdin.readline def main(): N = int(input()) cow = [None for _ in range(11)] answer = 0 for _ in range(N): a, b = map(int, inpu..

https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 시뮬레이션과 백트래킹으로 모든 조합을 만들면 된다. i번째가 i번째로 가는 시뮬레이션 부분은 어렵지 않지만 백트래킹으로 조합을 만들때 중복되는 거 없이 수를 최소한으로 줄여야 통과할수 있었다. #include #include using namespace std; int N, M, H; int ladder[32][12]; int answer; bool check() { int i, r, c; fo..

https://www.acmicpc.net/problem/15666 15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백트래킹 문제 4 # N & M (12) import sys; input = sys.stdin.readline def backtrack(lst=None): global N, M, nums, visit, answer if lst is None: lst = [] if len(lst) == M: answer.add(tuple([nums[i] for i in lst])) return for i in ..

https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백트래킹 문제 3 # N & M (9) import sys; input = sys.stdin.readline def backtrack(lst=None): global N, M, nums, visit, answer if lst is None: lst = [] if len(lst) == M: answer.add(tuple([nums[i] for i in lst])) return for i in ra..

https://www.acmicpc.net/problem/15657 15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 백트래킹이 조금 부족한거 같아서 푼 문제 2 # N & M (8) import sys; input = sys.stdin.readline def backtrack(lst=None, prev=0): global N, M, nums if lst is None: lst = [] if len(lst) == M: print(*[nums[i] for i in lst]) return for i in r..

https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 백트래킹이 조금 부족한거 같아서 푼 문제 # N & M (5) import sys; input = sys.stdin.readline def backtrack(ind, limit, size, nums, visit, lst=None): if lst is None: lst = [] if ind == limit: print(*[nums[i] for i in lst]) return for i in..

https://www.acmicpc.net/problem/3040 3040번: 백설 공주와 일곱 난쟁이 매일 매일 일곱 난쟁이는 광산으로 일을 하러 간다. 난쟁이가 일을 하는 동안 백설공주는 그들을 위해 저녁 식사를 준비한다. 백설공주는 의자 일곱개, 접시 일곱개, 나이프 일곱개를 준비한다. www.acmicpc.net 손풀기용 문제 combination으로 두개의 값을 고르고, 그 두개의 값을 뺐을때 100이 되는 값을 찾는다. 그 두개의 값을 제거한뒤에 모든 값을 출력하면된다. # import sys; input = sys.stdin.readline from itertools import combinations def main(): dwarves = [int(input()) for _ in range..

https://www.acmicpc.net/problem/24230 24230번: 트리 색칠하기 정점이 $N$개인 트리가 있다. 정점에는 1부터 $N$까지 번호가 붙어있다. 트리의 루트는 항상 1번 정점이며 맨 처음에는 모든 정점이 하얀색으로 칠해져 있는 상태이다. 하나의 정점에 색칠하면 해 www.acmicpc.net 트리 문제이다. 트리를 만들고 순회하면 된다. 특정 노드의 부모가 가진 색깔과 노드가 원하는 색깔이 다른 경우 1 을 더한값을 계속 올려주면 된다. import sys; input = sys.stdin.readline sys.setrecursionlimit(10**9) def order(cur_node, cur_color, parent, adj_list, color): ret = 0 if..

https://www.acmicpc.net/problem/17073 17073번: 나무 위의 빗물 첫째 줄에 트리의 노드의 수 N과 1번 노드에 고인 물의 양을 의미하는 정수 W가 주어진다. (2 ≤ N ≤ 500,000, 1 ≤ W ≤ 109) 다음 N-1줄에 걸쳐, 트리에 존재하는 간선의 정보가 U V의 형태로 주어진다 www.acmicpc.net 트리 문제이다. 입력으로 주어지는 값은 양방향 그래프이고 인접리스트를 사용해서 노드끼리 연결 시킨다. 그리고 트리를 순회할때 parent 노드와 다른 번호의 노드만 순회를 하면 leaf 노드를 찾을수 있다. leaf node를 찾으면 1을 리턴해주고 이 값들을 모두 더해주면 leaf 노드의 개수를 찾을수 있다. import sys; input = sys.s..