IT recording...

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 풀이 최적화 문제에 마주쳤는데, N이 엄청나게 크다 ⇒ 이분탐색 사용하기 → 나무의 수가 최대 1,000,000개로 매우 큼. 그냥 순차 탐색은 O(N)의 시간 복잡도를 가지지만 이분탐색은 O(log2N)의 시간복잡도를 가지기 때문에 무조건 이분탐색 써야함 기준은 '자를 높이(cut)'임. 따라서 start = 0, end = max(tree)로 설정 이분탐..

15686번: 치킨 배달 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 풀이 치킨집 M개만큼만 남겨가면서 치킨거리가 얼마인지 각각 계산해야하는데 결론은 다 해봐야 한다. combination사용해서 모든 경우를 다 하며 최소인 경우를 찾는다. import sys from itertools import combinations def input(): return sys.stdin.readline().rstrip() N,M = map(int,input().split(" ")) maps = [l..

11660번: 구간 합 구하기 5 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 풀이 계산이 최대 100,000번까지이기 때문에 다 계산하는건 사실상 불가 그렇다면 dp테이블을 이용해보자 00부터 특정 칸까지의 구간합을 이용할건데, 계산하는 범위가 맨 첫 줄부터가 아님 → 한 row단위로 끊어서 빼서 계산하자 00을 포함할 때, 한 칸 일 때의 예외 처리 import sys def input(): return sys.stdin.readline().rstrip() N,..

https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 풀이 처음에는 permutation써서 모든 순열 쌍을 다 구해서 풀이했는데 역시나 메모리 초과 최대 9개 쌍의 순서를 (9의9승) 다 비교하려하다니 아주 멍청스했다 이 문제는 greedy문제로 다 해보는 것이 아니라 자릿수의 중요도를 매겨서 최대 합을 구하는 문제였다. 10의 자릿수마다 중요도가 다르므로 그 중요도를 각 알파벳마다 저장해두어야 한다. 어차피 나중에 다 합치는 것이므로 한 알..

11659번: 구간 합 구하기 4 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 풀이 처음에 아 뭐야 완전 쉽네? 하고 그냥 했다가 시간초과 당함 그래서 dp 테이블 써서 이전 꺼 저장하고 다시 사용하는 방법으로 했는데 이번엔 메모리 초과 그도 그런게 N이 1,000,000까지인데 최악의 경우 N*N의 크기일 수 있으니 메모리 초과는 당연.. index 0부터 n까지의 누적합을 저장해두고 빼는 것으로 하자! 메모리 초과 dp코드 더보기 import sys sys.setrecursionl..

https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 풀이 빈칸을 채워야 하는 것이므로 빈 칸의 좌표를 가지고 있는 list를 만든다. 해당 빈 칸들을 돌며 가능한 후보들을 찾는다. 해당 빈 칸에 가능한 후보를 sdoku맵에 업데이트한 후 그 다음 빈 칸을 검사하러 간다. 만약 가능한 후보가 없다면 해당 route는 자동으로 종료된다. sdoku판을 다시 원상복구 시킨 후 다음 candidate를 검사한다. 마지막 zero까지 다 채워넣는 것이 성공..

1759번: 암호 만들기 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 풀이 딱 보자마자 combination 이용해야겠다고 생각 든 문제 import sys from itertools import combinations def input(): return sys.stdin.readline().rstrip() L,C = map(int,input().split(" ")) letter = list(input().split(" ")) standard_vowels = {"a","e","i","o","u"} vowel =..

1920번: 수 찾기 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net import sys def input(): return sys.stdin.readline().rstrip() N = int(input()) A = set(list(map(int,input().split(" ")))) M = int(input()) num = list(map(int,input().split(" "))) for n in num: if n in A: print(1) else: pri..

1039번: 교환 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 처음에 문제를 보고 dfs를 사용하면 되겠군. 했는데 중간에 잘 안풀리자 갑자기 아니 뭐야 greedy로 풀면 되잖아?? 라면서 길을 잘못 들었다. 흠.. 다시 생각해보니까 바꾼 것 중에서 최대값이 나오려면 무슨 공식이 있는 것이 아니라 처음부터 끝까지 다 해봐야 한다. 1,000,000 이라는 숫자도 보면 다 해보고 싶게 생긴 숫자다. #1 . dfs만 사용 문자열의 크기 M의 이중for문을 돌면서 모~~~~~든 경우를 다 돌며 answer를 전역변수로 두어 k만큼 수행했을 때 현재까지의 Max를 갱신하도록..

1103번: 게임 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net import sys sys.setrecursionlimit(10**6) #python3는 10**6까지 , pypy3는 10**5까지 / 아니면 메모리초과 def input(): return sys.stdin.readline().rstrip() N,M = map(int,input().split(" ")) B = [list(input()) for _ in range(N)] #print(B) visited = [[False]*M for _ in r..