0과 1의 쉼터

풀이 일반적으로 범위가 넓을수록 최솟값과의 곱으로 인해 점수가 작을것이다. 때문에, 최솟값을 기준으로 나눈 영역(최솟값을 제외한 나머지 영역)에 대해 점수를 구할 때 높은 점수를 기대할 수 있다. 그러기 위해서는 먼저, 구간별로 가지는 합과, 최솟값을 구해야 한다. leaf를 입력받은 후 초기화를 진행해주자. pair에 합과, 최솟값을 가지는 요소의 index를 넣어줬다. 위에서 언급했듯, 최솟값을 기준으로 나눈 영역의 범위를 설정하기 위해서 value가 아닌 index를 넣어줬다. 구간별로 점수를 계산하기 위해 query를 작성해주었다. 주어진 구간에 대한 합과 최솟값의 index로 이루어진 pair를 반환한다. 초기화 단계에서는 올바르지 않은 요소를 접근하지 않는다. 하지만 위의 query는 올바르지..

풀이 트리로 주어지는 목차의 정보를 글머리 번호 형태로 바꾸면 되는 문제다. 아래 조건에 따라 변환할 수 있다. i 번째 수가 i - 1번째 수보다 작다면, 상위 글머리 번호부터 변환해주어야 한다. i 번째 수가 i - 1번째 수보다 크다면, 글머리 번호 형태에 따라 1로 변해야 한다. i 번째 수가 i - 1번째 수와 동일하다면, 이미 존재하는 목차이므로 i - 1번째 수의 글머리 번호 형태 + 1로 변해야 한다. 먼저 i번째 수가 i - 1번째 수보다 작은 경우다. 상위 글머리 번호부터 변환해주어야 하기에 이전에 기록된 하위 글머리 번호에 대해 누적된 수들을 0으로 초기화 하는 과정이 시간초과의 원인이 되었다. 이번 기회에 알게 된 사실인데, 문제를 틀렸거나 부분점수를 얻은 경우 '내 제출' 란에서 ..

풀이 스택이란 항아리 처럼 나중에 집어넣은 것이 먼저 나오는 제한적 접근 나열 구조이다. LIFO(Last In First Out) 형식이며, 기본 개념을 구현만하면 된다. 단, 한 줄에 하나씩 출력해야 한다는 것을 명심하자 pop 명령을 실행하기 전에 스택이 비었는지 확인하기 위해 empty 명령어만 함수로 구현했다. 실제 메모리에 대한 참조를 해제할 필요 없이, 변수 top을 사용해 값을 가르키는데 제한을 두었다. 소스코드 소스코드 보기 출처 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net..

풀이 문자열의 길이가 폭발 문자열의 길이보다 크거나 같을 때, 폭발 문자열을 포함하고 있으면, 폭발 문자열의 길이만큼 index를 감소시키는 방식으로 출력할 문자열을 만들어주었다. 최종적인 index만큼 출력을 해줘도 되고, 마지막에 '\0'을 삽입해 문자열의 끝을 알려줘도 된다. 소스코드 #include #include char str[1000001], ans[1000001], explosion[37]; int main(){ scanf("%s %s", str, explosion); int len = strlen(str), exp_len = strlen(explosion), idx = 0; for (int i = 0; i = e..

풀이 0을 입력받으면 pop, 아니면 push이다. 연산 효율을 위해 일단 입력받고 0이면 top를 -2만큼 감소시켰다. 소스코드 #include int main(){ int K; scanf("%d", &K); int stack[K], top = -1, sum = 0; for (int i = 0; i < K; i++){ scanf("%d", &stack[++top]); if (!stack[top]) top -= 2; } for (int i = 0; i

풀이 '(', '[' 일때는 stack에 삽입해주고, ')', ']' 일때, top이 -1이 아니고, stack[top]에 '(', '['가 있을때, top를 감소한다. 만약 그렇지 않다면, "] ["나 ") (" 처럼 짝이 안맞는 경우이므로 출력을 위해 top값을 -2로 갱신하고 반복문을 빠져나온다. 소스코드 #include #define MAX 101 int main(){ char str[MAX], stack[MAX]; while (1){ gets(str); if (str[0] == '.') break; int top = -1; for (int i = 0; str[i] != '.'; i++){ if (str[i] == '(' || str[i] == '[') stack[++top] = str[i]; e..

풀이 다음과 같은 규칙이 존재한다. 둘째 줄부터 입력받은 수까지 push를 해주어야 하며, push는 이전에 입력된 수보다 큰 수가 입력될 때만 발생한다. push가 발생하거나, 이전에 입력된 수보다 작은 수가 입력될 경우 불필요해 생략한 후 pop가 발생해야한다. 만약, pop이 발생하지 않았다면, 스택을 이용해 수열을 만들 수 없다는 의미이다. 따라서, 둘째 줄부터 입력받는 n개의 수들을 저장할 필요가 없다. 소스코드 #include int main(){ int n; scanf("%d", &n); int stack[n], top = 0, val, idx = 0, num = 0; char op[2*n]; for (int i = 0; i < n; i++){ scanf("%d", &val); for (in..

풀이 입력된 괄호이후 막대기의 개수를 top라고 하고, 다음과 같은 조건에 의해 result에 막대기의 개수를 더해주면 된다. ')'이전에 '('가 입력되었으면, 쇠막대기가 아니라 레이저이므로 --top한 값을 result에 더해준다. 쇠막대기를 의미하는 ')'만 입력 되었으면, 쇠막대기의 끝 부분에 도달한 것 이기 때문에 1개만 더하고, 현재 막대기의 개수를 1개 감소시킨다. 소스코드 #include #define MAX 100001 int main(){ char stack[MAX]; int top = 0, result = 0; scanf("%s", stack); for (int i = 0; stack[i] != '\0'; i++) if (stack[i] == '(') top++; else{ if (i..