개발하는 사막여우

https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 소스코드 풀이 ★ 전형적인 DP문제였습니다 ! 풀이부터 말하자면 n이 가질 수 있는 이친수의 개수는 n-1의 이친수 개수 + n-2의 이친수 개수입니다. ex) ★ n이 6일 경우 이친수의 수는 8입니다. n으로 만들 수 있는 이친수의 개수를 dp에 저장한 뒤 이를 가지고 점화식을 세워보면, dp[n] = dp[n-1] + dp[n-2]로 세울 수 있고 이는 다음과 같이 적용됩니다 ! ..

https://www.acmicpc.net/problem/25556 25556번: 포스택 포닉스가 순열을 청소할 수 있으면 YES, 불가능하다면 NO를 출력한다. www.acmicpc.net 소스코드 풀이 ★ 핵심은 각각의 스택의 최상단 값보다 스택에 넣으려고 하는 값이 커야한다는 것입니다 ! ex) 예제와 같이 5,4,3,2,1이 주어졌을 때 스택 4개에 5,4,3,2가 각각 들어가고 1이 아무 스택에나 들어간다고 하더라도 그 스택들을 하나씩 뽑아서 오름차순을 만들 수 없습니다 ! [5],[4],[3],[2,1]처럼 수가 들어간 경우 4번째 스택에서는 1이 먼저 나오고 2가 나오기 때문에 이미 내림차순 형태가 되어버립니다. ★ 구현하는 과정에서 for ~ else 구문을 사용하였습니다. 만약 for문이..

https://www.acmicpc.net/problem/27497 27497번: 알파벳 블록 첫째 줄에 버튼을 누른 횟수 $N$이 주어진다. $(1 \leq N \leq 1\,000\,000)$ 둘째 줄부터 $N$개의 줄에는 버튼을 누른 순서대로 누른 버튼에 대한 정보를 주며 아래와 같은 형식으로 주어진다. 1 c : 문자열 www.acmicpc.net 소스코드 풀이 ★ 누르는 버튼에 따라 순서대로 들어오는 알파벳을 기록할 stack과 문자를 만드는 큐를 따로 만들어 풀이를 진행했습니다. 버튼 2의 경우에는 문자열의 앞에 알파벳을 추가해야 하고, 버튼 3을 눌렀을 경우 문자열의 앞에서 알파벳을 제거해야 하기 때문에 양방향 push, pop이 가능한 큐를 사용하였습니다. ★ 문자열에 추가될 때 해당 알파..

https://www.acmicpc.net/problem/3111 3111번: 검열 첫째 줄에 단어 A가, 둘째 줄에 텍스트 T가 주어진다. A와 T는 알파벳 소문자로만 이루어져 있고, A는 최대 25자, T는 최대 300,000자이다. www.acmicpc.net 소스코드 풀이 ★ 해당 문제를 푸시기 전에 다음 문제를 먼저 풀어보는 것을 추천드립니다 ! 스택 안에서 주어진 단어를 찾는 경우, 단어의 길이만큼 스택 위에서부터 찾는 방법을 익힐 수 있기 때문입니다 :) https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1..

https://www.acmicpc.net/problem/16496 16496번: 큰 수 만들기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 리스트에 포함된 수가 주어진다. 수는 공백으로 구분되어져 있고, 1,000,000,000보다 작거나 같은 음이 아닌 정수 이다. 0을 제외한 나 www.acmicpc.net 소스코드 풀이 ★ 핵심은 입력 받은 리스트의 원소들을 문자열 형태로 바꾸고(사전 순으로 크기를 비교하기 위헤), 대소 비교를 통해 정렬해주는 것입니다 ! ex) [3,30,34,5,9]를 문자열 형태로 바꾼 뒤, lambda x:x*3을 기준으로 내림차순 정렬하게 되면, [999,555,343434,333,303030] => [9,5,34,3,30] 형태로 정렬됩..

https://www.acmicpc.net/problem/9576 9576번: 책 나눠주기 백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 N권이었다. 책이 너무 많기 때문에 백준이는 책을 구분하기 위해 각각 1부터 N까지의 www.acmicpc.net 소스코드 풀이 ★ 주어진 구간 i,k중 k를 기준으로 정렬하는 이유는 책을 최대한 많은 사람들에게 줘야 하며 범위가 더 크기 때문에 책을 가져갈 수 있는 범위 또한 넓기 때문입니다. ★ 이때 오름차순 정렬을 하는 이유는 예를 들어 ex) n = 3, m = 3, [1,2], [1,3], [1,2] 와 같이 책을 가져갈 수 있는 구간이 주어진다면 내림차순 정렬을 하게 될 경우 [1,3]은 1번 책, [..

https://www.acmicpc.net/problem/17952 17952번: 과제는 끝나지 않아! 성애는 이번 학기에 전공을 정말 많이 듣는다. 이로 인해 거의 매일을 과제를 하면서 보내고 있다. 그런데도 과제가 줄어들 기미가 보이지 않는데, 바로 분단위로 과제가 추가되고 있기 때문이 www.acmicpc.net 소스코드 풀이 ★ 점수를 저장하는 스택과, 시간을 저장하는 스택을 따로 만들어줬습니다. ★ 과제가 없는 경우에는 과제를 할 수 있기 때문에 시간 스택의 맨 위에 있는 시간을 -1 해줍니다. 이 때 시간의 값이 1이 되면 과제가 끝났다는 것이기에 점수와 시간을 각각의 스택에서 제거해주고, 점수는 출력 값 변수에 + 해줍니다. ★ 과제가 들어오는 경우는 해당 과제를 먼저 해줘야 하기 때문에 스..

https://www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net 소스코드 풀이 ★ 카드들의 합을 최소로 만들기 위해서는 가장 작은 수 두개를 더한 뒤, 그 수를 덮어쓰는 방법을 써야 합니다 ! ★ 가장 작은 두 수를 찾기 위해 놀이를 진행할 때마다 오름차순 정렬을 해줍니다. ★ 그 후 합을 변수 res에 저장하고, 각각의 카드에 덮어 써주면 됩니다 :)

https://www.acmicpc.net/problem/17413 17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net 소스코드

https://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 소스코드 풀이 ★ 처음 생각했던 방식은 최솟값을 구해야 하기에 입력 받은 저울 추를 오름차순 정렬하고, 저울추로 구할 수 있는 모든 경우의 수를 구한 뒤, 구하지 못하는 값들 중 최솟값을 출력하는 방식이었습니다 ! ex) [A,B,C] => A, A+B, A+C, B+C, A+B+C 하지만 당연하게도 시간초과가 발생했고, 입력 받은 예제를 토대로 위와 같은 방식을 출력해보니 다음과 같은 결과를 얻을 수 있었..