IT recording...

1806번: 부분합 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 풀이 처음에는 0항부터 현재 항까지의 부분합을 구해놓은 후 이 차이를 이용하여 시간초과를 해결하려 하였다. 근데 그렇게 해도 될 것 같긴한데 어쨌든간에 최악의 경우 O(N*N) 시간이 걸린다는 점을 간과했다. 투포인터를 사용하여, start를 증가시키면서 한 번이라도 end가 N-1까지 간다면 S를 만들 수 없다는 점을 이용하자 start와 end를 증가시키며 진행하고, '연속된 수들의 합' 을 이용하는 것이므로 양 끝 값을 더..

2470번: 두 용액 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 풀이 모든 조합의 수를 구한다는건 말도 안됨, 근데 모든 경우의 수를 다 하는 것 밖에 없는데 그렇다면 투 포인터 이용! 하나씩 포인터를 이동해가며 절댓값이 최소가되도록 하는 (양,음을 이용해서 판별) 포인터를 이동시키고, 그 들 중 최솟값을 저장하여 출력한다. 포인터를 이용할 것 이므로 리스트를 소팅한다. 여기서 투 포인터는 양쪽 liquid 인덱스이고, 판단 기준은 '절댓값이 최소가 된다' → '음,양 ..

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 =..

9663번: N-Queen 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 일단 체스판에 Queen을 두는 방법은 가로쭉,세로쭉,대각선쭉에 퀸을 두지 않는 것이다. 이것은 같은 행 혹은 같은 열에 Queen을 두지 않게 하고 + 대각선 검사 를 진행하면 된다. 행,열을 이차배열로 관리할까 했지만 어차피 한 행,열 당 하나씩 밖에 못 놓는 성질을 이용하여 행 혹은 열을 배열의 index로, 나머지 하나를 value로 관리하여 메모리를 줄인다. 0행을 기준으로 시작하여 0열,1열,2열...n-1열까지 queen을 넣으며 모..