투투

문제 N개의 수가 있고 +, -, x, ÷ 네 개의 연산자가 있다. 각각의 연산자 개수는 한정적이고 이를 활용하여 N개의 수에 연산을 적용했을 때 최댓값과 최솟값을 구하라. 연산자는 수의 개수보다 많을 수 있다. 단, 연산자 우선순위는 적용하지 않는다. => 연산자 끼워넣기 (1)은 N개의 수가 있다면 N-1개의 연산자가 있었지만 이 문제는 그 이상의 개수가 있을 수 있다. 입력 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1보다 크거나 같고, 4N보다 작거나 같은 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다. 출력 ..

www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net 접근 python의 heapq를 사용해보았다. 최대힙이 되도록 heap 자료구조에 넣고 0을 입력할 때마다 최댓값을 출력한다. 구현 N개의 수를 입력한다. 0이 입력되었을 때 heap이 비어있으면 0을, 아니라면 최댓값을 출력한다. 이외의 수가 입력된다면 heap 자료구조에 최댓값이 위에 있도록 마이너스 값과 튜플형태로 넣어준다. import sys import heapq input = sy..

문제 N개의 통나무가 원형으로 놓여져있다. 통나무 위를 건너뛰어다니려고할 때 통나무를 어떻게 놓는지에 따라 난이도가 결정된다. 난이도는 옆에 있는 통나무와의 높이차이로 결정된다. 이때 가장 큰 차이가 난이도가 되며 첫 번째 통나무와 마지막 통나무도 서로 연결되어있는 것이다. 통나무를 적절하게 놓아서 가장 최소의 난이도를 만들자. 입력 입력은 T개의 테스트 케이스로 이루어져 있다. 첫 줄에 T가 주어진다. 이어지는 각 줄마다 첫 줄에 통나무의 개수를 나타내는 정수 N(5 ≤ N ≤ 10,000), 둘째 줄에 각 통나무의 높이를 나타내는 정수 Li가 주어진다. (1 ≤ Li ≤ 100,000) 출력 각 테스트 케이스마다 한 줄에 주어진 통나무들로 만들 수 있는 최소 난이도를 출력하시오. 접근 통나무를 어떻게..

programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 접근 최소로 가기위해서는 웅덩이를 피해 오른쪽 또는 아래로만 이동해야한다. 따라서 각 지점으로 올 수 있는 경우의 수를 메모를 해둔다. 즉, 왼쪽과 위의 경로에 대한 경우의 수를 더해주도록 한다. 구현 시작점부터 도착지점까지 경로에 대한 경우의 수를 구한다. 만약 현재 위치가 puddles에 포함되어있다면 continue하고, 그렇지 않다면 현재 경우의 수를 왼쪽 ..

programmers.co.kr/learn/courses/30/lessons/12927?language=python3 코딩테스트 연습 - 야근 지수 회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도 programmers.co.kr 접근 초기에 접근했던 방법은 n시간만큼 works에서 최댓값을 찾아서 -1씩 해주는 것이었으며 효율성테스트에서 시간초과가 발생했다. 이후 시간이 많이 남았는데 works는 모두 0일 때 계속 검사를 하게되기 때문에 합이 0일 때는 break를 했지만 시간초과가 발생했다. 따라서 어떤 부분에서 최적화를 진행해야할지 생각을 하게되었고,..

문제 상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다. 폭발은 다음과 같은 과정으로 진행된다. 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다. 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다. 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다. 상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다. 폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다. 입력 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,00..

문제 N 개의 막대 기둥이 일렬로 세워져 있다. 기둥들의 폭은 모두 1 m이며 높이는 다를 수 있다. 이 기둥들을 이용하여 양철로 된 창고를 제작하려고 한다. 창고에는 모든 기둥이 들어간다. 이 창고의 지붕을 다음과 같이 만든다. 지붕은 수평 부분과 수직 부분으로 구성되며, 모두 연결되어야 한다. 지붕의 수평 부분은 반드시 어떤 기둥의 윗면과 닿아야 한다. 지붕의 수직 부분은 반드시 어떤 기둥의 옆면과 닿아야 한다. 지붕의 가장자리는 땅에 닿아야 한다. 비가 올 때 물이 고이지 않도록 지붕의 어떤 부분도 오목하게 들어간 부분이 없어야 한다. 그림 1은 창고를 옆에서 본 모습을 그린 것이다. 이 그림에서 굵은 선으로 표시된 부분이 지붕에 해당되고, 지붕과 땅으로 둘러싸인 다각형이 창고를 옆에서 본 모습이다..

문제 1번부터 6번 줄이 있는 기타가 있다. 기타의 한 줄에는 P개의 프렛으로 나누어져있고 프렛도 1번부터 P번까지 번호가 있다. 어떤 줄의 프렛을 여러 개 누르고 있다면 가장 높은음만 출력된다. 손가락으로 프렛을 한 번 누르거나 떼는 동작이 손가락을 한 번 움직였다고 했을 때 어떠한 멜로디를 연주하는데 손가락을 가장 적게 움직이는 횟수를 구하라 입력 첫째 줄에 멜로디에 포함되어 있는 음의 수 N과 한 줄에 있는 프렛의 수 P가 주어진다. (N ≤ 500,000, 2 ≤ P ≤ 300,000) 다음 N개 줄에는 멜로디의 한 음을 나타내는 두 정수가 주어진다. 첫 번째 정수는 줄의 번호이고 두 번째 정수는 그 줄에서 눌러야 하는 프렛의 번호이다. 입력으로 주어진 음의 순서대로 기타를 연주해야 한다. 출력 ..

문제 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다. X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다. 예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다. ‘()’ 인 괄호열의 값은 2이다. ‘[]’ 인 괄호열의 값은 3이다. ‘(X)’ 의 괄호값은 2×값..

문제 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다. 출력 총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다. 접근 이 문제를 통해 누적합을 활용하여 구간합을 구하는 법을 알 수 있었다. 5개의 수열이 있을 때 두 번째 수부터 이전의 까지 누적합을 구해 기록해두고, (i, j)의 구간합을 구할 때는 i가 가리키는 수에서 j-1이 가리키는 수를 빼주면 구간합이 된다. 구현 - 입력을 받고나서 바로 누적합을 구하여 기록한다..