본문 바로가기

PS221

[백준 02800] 괄호 제거 [Python] 문제어떤 수식이 주어졌을 때, 괄호를 제거해서 나올 수 있는 서로 다른 식의 개수를 계산하는 프로그램을 작성하시오.이 수식은 괄호가 올바르게 쳐져 있다. 예를 들면, 1+2, (3+4), (3+4*(5+6))와 같은 식은 괄호가 서로 쌍이 맞으므로 올바른 식이다.하지만, 1+(2*3, ((2+3)*4 와 같은 식은 쌍이 맞지 않는 괄호가 있으므로 올바른 식이 아니다.괄호를 제거할 때는, 항상 쌍이 되는 괄호끼리 제거해야 한다.예를들어 (2+(2*2)+2)에서 괄호를 제거하면, (2+2*2+2), 2+(2*2)+2, 2+2*2+2를 만들 수 있다. 하지만, (2+2*2)+2와 2+(2*2+2)는 만들 수 없다. 그 이유는 쌍이 되지 않는 괄호를 제거했기 때문이다.어떤 식을 여러 쌍의 괄호가 감쌀 수 있다... 2024. 3. 22.
[백준 02075] N번째 큰 수 [C/C++, Python] 문제 N×N의 표에 수 N2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. N=5일 때의 예를 보자. 이러한 표가 주어졌을 때, N번째 큰 수를 찾는 프로그램을 작성하시오. 표에 채워진 수는 모두 다르다. 입력 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. 출력 첫째 줄에 N번째 큰 수를 출력한다. 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이.. 2024. 3. 20.
[Algospot] CLOCKSYNC [C/C++] 문제 algospot.com :: CLOCKSYNC Synchronizing Clocks 문제 정보 문제 그림과 같이 4 x 4 개의 격자 형태로 배치된 16개의 시계가 있다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있다. 이 시계들이 모두 12시를 가리키도록 algospot.com 풀이 버튼을 누르는 순서는 중요하지 않지만, 4번 누르면 시계가 원래대로 돌아오기 때문에 O(4^10)인 완전 탐색이 가능하다. 우선 버튼을 눌렀을 때 시간이 변하는 시계들을 다음과 같이 정리해주자. 각 배열의 첫번째 요소는 배열의 길이를 의미한다. 버튼을 누르는 횟수는 4회 미만이므로 버튼을 눌렀을 때 시계를 바로 업데이트 하는 것이 아닌 다음 버튼을 누르는 Recursive Call을 해서 분기를 .. 2024. 3. 15.
[Algospot] BOARDCOVER [C/C++] 문제 algospot.com :: BOARDCOVER 게임판 덮기 문제 정보 문제 H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이 algospot.com 풀이 주어지는 보드의 빈 공간에 3칸으로 만들어진 'ㄴ' 모양의 블럭으로 전부 다 덮는 경우의 수를 구하는 문제다. 한 위치에서 12개의 경우의 수가 주어지지만, 블럭을 순차적으로 놓기 때문에 한 방향에 대해서만 생각해도 충분하다. 위/왼쪽을 기준으로 채운다고 가정했을 때 필요한 블럭은 아래와 같다. 여러번 사용해야하므로 미리 만들어두자. 가장 왼쪽 위 부터 비어있는 공간을 찾으며 dfs를 진행하자. 블럭을 다 채웠다면 못찾고 종료하므.. 2024. 3. 14.
[백준 03273] 두 수의 합[Python] 문제 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000) 출력 문제의 조건을 만족하는 쌍의 개수를 출력한다. 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은.. 2024. 3. 11.
[백준 01182] 부분수열의 합 [Python] 문제 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 풀이 N개의 정수에 대한 조합 가능한 모든 부분 수열을 찾고, 부분 수열의 합이 S와 일치하는 경우를 찾아야 한다. 크기가 양수인 부분 수열에 대한 합비교 이므로 S가 0일 때 부분 수열의 길이가 0인 경우는 제외해야 한다. combinations 사용 버전 N개의 정수로 이루어진 수열에 대해 1 ~ N개로 생성할 수 있는 조합을 전부 생성해 합을 비교하는 방법이다. 가장 짧고 간결한 방법이다. 부분 수열의 합이 S와 일.. 2024. 3. 3.

티스토리툴바