잡담연구소

www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net IDEA 가장 긴 증가하는 부분 수열을 구하는 문제다. A전깃줄의 위치 , B전깃줄의 위치 순으로 입력을 받는데 , A전깃줄의 위치에 대해서 오름차순으로 정렬해보면 아래와 같은 그림이 나온다. 왼쪽 A전깃줄번호를 인덱스로 가지는 배열이 있고, 그 값이 B전깃줄번호라고 생각해보자. [8,2,9,1,4,6,7,10] 이 된다. 이 중 전깃줄이 교차하지 않기 위해서는 i < j 라면 arr[i] < arr[j] 여야한다. ..

www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net IDEA 숫자들 사이에 어떤 기호가 들어갈지 백트랙킹으로 구현하는 문제인 거 같다. 연산자를 해당 숫자 (0 ~3) 으로 cal이라는 배열에 저장 연산자가 1 0 2 1 식으로 주어진다. 인덱스 번호에 맞춰 cal 이라는 연산자 배열에 해당 횟수만큼 저장한다. 0 2 2 3 이렇게 cal에 들어간다. cal 인덱스로 순열을 구현한다. 숫자가 n개면 연산자는..

www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net IDEA 연속된 수열의 최대 합 문제로 dp로 풀 수 있다. dp[i] 에는 배열 arr[i] 까지의 연속된 수의 합 중 최댓값을 저장하자. sum이 음수가 될 때는 그 이후 값부터 새로시작하는 게 더 큰 값이다. sum 의 부호와 상관없이 계속 더할 때 arr 5 -7 2 sum 5 -2 0 sum이 음수일 경우 새롭게 시작할 때 (sum = 0 초기화 후 새로운 arr 값 더해줌 ) arr 5 -7 2 sum 5 -2..

www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net IDEA 다신 만나고싶지 않다,,,, 이렇게 문자열 처리?로 시작하는 거 너무 힘들어.,,,, R 이면 숫자를 뒤집고 , D면 맨 앞에 있는 숫자를 버리는 걸 반복해 최종 결과를 출력하는 문제이다. 문제에서 배열을 뒤집으라고 했다가 뒤집으면 인생이 피곤해진다. 뒤집은 결과물을 출력하는 거기 때문에, 몇 번 뒤집혔냐에 따라 앞에서부터 출력하느냐, 뒤에서부터 출력하느냐의 문제이기때문에 deque 덱을 써야한다. string으로 배열을 입력받는다. str[i] 가 수라면 ..

IDEA 맨 처음에는 일단 써봤다. 1666 2666 3666 4666 5666 6660 6661 ......... 규칙성을 찾을수가 없어서 666을 기준으로 앞에는 1 ~ 9를 더해주고 뒤로는 0~9를 더해줘서 리스트에 넣어준 후 정렬을 통해 K번째 종말의 수를 찾아주면 되지 않을까? 생각을 해보았다. 구현하기 귀찮을 거 같아서 다른 방법이 없을까 생각을 해보았다. 우리가 찾는 수는 최대 10000번째 수이다. 그래서 완전탐색? 브루트포스를 이용해서 최소 666부터 숫자를 하나하나 늘려가며 6이 몇개인지 확인해도 주어진 시간 안에 돌아갈 거라고 생각했다. while 반복문을 통해서 숫자를 하나하나 늘려가며 6이 연속으로 3개 이상 있는지 확인한다. 6이 연속으로 3개 이상 있는 지 어떻게 확인하냐? 라..

www.acmicpc.net/problem/21562156번: 포도주 시식효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규www.acmicpc.netIDEA마실 수 있는 최대 포도주 양을 구하는 문제다. 특히, 연속된 세개의 잔을 마실 수 없다라는 조건만 잘 맞춰주면 된다.그래서 옛날에 계단 오르기를 풀었던 거처럼 똑같이 풀면 되는 거 아니야? 라고 생각했다.그래서 dp[i] : i번째 포도주잔을 마셨을 때의 최대 포도주 양 을 저장해주고, dp[i-2] + arr[i] : i-2번째 포도주잔을 마셨을 때의 최대 포도주 양 + i번째 포도주잔의 양 세번은 연속으로 ..