링크: https://www.acmicpc.net/problem/10799문제스택 문제로 유명한 한국정보올림피아드(KOI) 2015 지역본선 문제, 쇠막대기입니다. 사실 스택 없이 풀리는 문제지만요.문제를 읽어보면 쇠막대기의 왼쪽 끝은 여는 괄호, 오른쪽 끝은 닫힌 괄호로 표시하여, 레이저 "()"에 의해 잘려진 막대기 조각이 총 몇 개인지 구하는 문제입니다.잘못된 모양은 없다고 하니 스택으로 별다른 검증은 안해도 됩니다.풀이먼저 풀이의 중간 단계를 생각해봅시다. 문자열 "((()()))"은 쇠막대기가 2층으로 쌓인 형태일 것이고, 위 사진처럼 레이저(노란색 점선)에 의해 잘려나갈겁니다. 여기서 첫 번째 레이저에 집중해봅시다.첫 번째 레이저가 발사된다면 1층에서 2조각, 2층에서 2조각으로 나뉘어서 총 ..

링크: https://www.acmicpc.net/problem/16236문제매번 어떤 물고기를 먹어야 할 때, 현재 위치를 중심으로 BFS를 한다.조건에 만족하는 물고기가 있다면 가장 위, 가장 왼쪽에 있는 물고기를 고른 후 그 위치로 이동한다.현재 아기 상어의 크기는 물고기를 먹은 양만 알면 크기를 알 수 있기 때문에 미리 구해서 사용했다. (먹을 때마다 갱신해도 상관없음)코드

링크: https://www.acmicpc.net/problem/16235문제시뮬레이션여름과 겨울은 양분을 더하는 것밖에 영향을 안 미치기 때문에 같이 처리할 수 있다.링크드리스트로 정렬된 상태 유지 + 나무 개수를 압축하여 표현나무의 개수를 압축해도 수명이 끝난 나무를 확인하는 것 때문에 시간복잡도는 거의 변화가 없어서 고민이 많았는 데, 항상 크기가 1인 나무들이 생기므로 링크드리스트의 앞과 뒤만 잘 관리하면 된다는 것을 Nada님의 코드를 보고 깨달았다.코드

링크: https://www.acmicpc.net/problem/11058출력 결과에 영향을 미치는 연산이 A를 그냥 누르는 거랑(+1), Ctrl-V (+복사했던 크기) 인데 클립보드에 복사해놓은 크기때문에 재귀로 짜는데 애를 먹었다. 복사한 크기만큼 늘어나기 때문에, Ctrl-V 를 하기 위해서는 이전에 Ctrl-A, Ctrl-C 가 꼭 필요하다. 문제에 적힌 연산을 순서대로 A, S, C, V 라고 한다면 \(N=6\)인 경우는 아래와 같이 가능하다. AAAAAAAAASCVAASCVVASCVVV 이 정도가 의미있는 타이핑인거같다. 타이핑을 \(n\)번한 것을 \(f(n)\)이라 하자. 그럼 위 4줄은 각각 \(f(5)+1\), \(f(3)∗2\), \(f(2)∗3\), \(f(1)∗4\) 이다. $..

링크: https://www.acmicpc.net/problem/1509문제\(dp[i]\) = \(i\)번째 위치에서 가능한 팰린드롬 분할의 최소 개수\(isPaline[i][j]\) = \(i~j\) 가 팰린드롬인지 여부 예제에도 끼워져있지만 AABDBADD 와 같은 경우의 처리때문에 여러 경우를 탐색해야한다. 이것을 분할하는 경우는 아래와 같다.A - A - B - D - B - A - D - D A - A - B - D - B - A - DD A - A - BDB - A - D - D A - A - BDB - A - DD A - ABDBA - D - D A - ABDBA - DD AA - B - D - B - A - D - D AA - B - D - B - A - DD AA - BDB - A - ..

링크: https://www.acmicpc.net/problem/3079코드

[이전 블로그]에서 글 옮김 링크: https://www.acmicpc.net/problem/1766풀이처음에는 문제의 접근 방향을 후위순회처럼 생각했다. 어떤 x번째를 하기 위해서 그 이전것을 무조건 해결해야하는 방식. 틀리고 나서 문제를 다시 이해했는데, 깨달은 테스트 케이스부터 말하자면 아래와 같다.5 3 4 1 2 3 5 3 내가 생각한 이 입력의 정답은 아래와 같다.2 4 1 5 3 1번보다 4번을 먼저 풀어야하고, 3번보다 2, 5번을 먼저 풀어야한다. 1번을 풀기 위해서 4번을 풀어야하는데, 같은 우선순위에서 4번보다는 2번이 쉽다. (둘 다 1개의 문제 앞에 있음)2번을 풀고 4번을 풀면, 1번이 풀리고 남은 5번을 풀면 3번이 풀린다. 처음에 생각한 대로라면 4 1 2 5 3 이 나와야하..

링크: https://www.acmicpc.net/problem/13701문제BOJ 15719 - 중복된 숫자를 비트로 해결하는 풀이와 같다. 엄밀히 말하면 이 문제가 더 먼저 만들어졌다.정확히 같은 풀이이므로 링크로 대체한다.다른 점이 있다면, 표현할 수의 범위가 \(2^{25}\)가 최대이므로 32비트 정수 배열의 크기가 \(2^{25}~/~32=1~048~576\)이면 된다.코드