likemath1997

(끝에 출력때문에 고생해서 블로그에 정리해두려고 한닷) 문제링크 : https://www.acmicpc.net/problem/5557풀이 및 사고모든 케이스를 깡으로 계산하면 2^100( +, -로 두 가지 경우가 계속 발생)로 시간 초과다.근데 문제에서 0에서 20까지만 결과값을 유지한다고 주어져서 최대 100*21의 복잡도를 가지는 배열로 풀 수 있었다. 01...20첫 번째 값    두 번째 값    ...    마지막 값     요런 배열을 만들어서 이전 줄을 다 순회하면서 1이상의 값(해당 경우의 수)일 때 현재 값으로 +/-한 값(인덱스)에 경우의 수를 더해주면 된다.(문제를 대충 읽어서 주어진 출력을 다 써서 0~20 사이의 값을 만들면 되는줄 알았는데 그게 아니고 입력 제일 마지막 값이 되..

(블로그로 정리된 자료가 없어서 문제 푸는 분들에게 도움이 될까 남겨봅니닷) 문제 링크 : https://www.acmicpc.net/problem/2412풀이 및 사고좌표를 받아서 y값, x값 순으로 정렬했다. 그리고 좌표가 정렬된 배열에서 index를 가지고 bfs를 돌렸다. y값 차이가 2초과면 멈추게 했다. 그리고 올라가기만 한다는 보장이 없어서 해당 index보다 앞과 뒤 둘 다 탐색했다.방문 처리는 좌표가 정렬된 배열과 같은 길이의 1차원 배열로 처리했다. (처음에는 전체 board를 저장하는 2차원 배열을 만드려고 했다가 x좌표가 1,000,000이고 y좌표가 200,000인데 메모리 제한이 128MB라 공간 복잡도 초과가 떴다.)코드const input = require('fs').read..

풀이 및 사고일단 누적합이라는 걸 알고 풀긴했다.. ㅎ문제에서 최대 한번의 오타를 냈다는 말이 있다. 이 말로 케이스(나올 수 있는 누적합 경우의 수)가 확 줄어들기 때문에 꼭 기억하고 풀어야 한다.처음 생각으로는 여는 괄호를 1, 닫는 괄호를 -1로 체크한 배열을 만들었다. 예시는 닫는 괄호가 더 많은 케이스라 누적합 처리를 하면 배열의 총합이 -2가 나온다.()(()))) ⇒ [1, -1, 1, 1, -1, -1, -1, -1] ⇒ [1, 0, 1, 2, 1, 0, -1, -2]여기서 문제가 어떤 괄호를 고쳐야 올바른 괄호쌍이 될 수 있는지 판단해야 하는 것이다.나올 수 있는 케이스를 먼저 생각해보면 누적합이 0, 2, -2인 케이스 밖에 없다.올바른 괄호쌍이거나 여는 괄호가 1개 많은 경우이거나 닫..

일단 모든 순열을 구해서 다음 순열을 찾으려면 순열에만 10000!(팩토리얼)을 쓰기 때문에 시간초과가 난다. 그래서 다른 방법을 써봤다. 기본적으로 a, b 두 스택을 이용했다. 스택을 나누는 대신 인덱스를 정해서 탐색해도 되지만, 직관적으로 이해가 잘돼서 스택을 이용했다. 이 방법을 이용하면 a, b 나누면서 N, b를 다시 탐색하면서 N으로 O(N)의 복잡도를 가진다고 생각한다. 기본 로직은 정답 코드에 적어놨다. 정답 코드 import sys n = int(sys.stdin.readline()) a = list(map(int, sys.stdin.readline().split())) b = [] # 12345 => a = [1, 2, 3, 4, 5], b = [] => b.append(a.pop()..