작심 24/7

https://www.acmicpc.net/problem/2841 2841번: 외계인의 기타 연주 문제 상근이의 상상의 친구 외계인은 손가락을 수십억개 가지고 있다. 어느 날 외계인은 기타가 치고 싶었고, 인터넷에서 간단한 멜로디를 검색했다. 이제 이 기타를 치려고 한다. 보통 기타는 1 www.acmicpc.net stack을 이차원으로 선언하여 줄 번호에 따른 프렛의 번호를 push해주면 된다. 같은 줄일 때 1. stack의 top > 현재 프렛 stack의 top < 현재 프렛 될때까지 pop (손가락 떼는 것 +1) 현재 프렛 push (손가락 누르는 것 +1) 2. stack의 top < 현재 프렛 현재 프렛만 push 해준다. (손가락 누르는 것 +1) 3. stack의 top = 현재 프렛..

2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 조건 중에 '오목한 부분이 없어야 한다'가 제일 중요하다. 오목한 부분이 없으려면 가장 긴 기둥을 기준으로 왼쪽이 계단식으로 올라가고 오른쪽은 계단식으로 내려가는 형태를 띄워야 한다. 값을 입력받으면서 시작 기둥과 끝 기둥, 그 사이에 있는 가장 긴 기둥들의 시작 위치와 끝 위치를 구한 뒤 결괏값에 가장 긴 기둥들의 넓이를 먼저 더해준다. stack의 top < 현재 기둥 이 되면 한 단계 상승하는 것이므로 pop해주고 현재 기둥을 push해준 ..

1725번: 히스토그램 문제 히스토그램에 대해서 알고 있는가? 히스토그램은 아래와 같은 막대그래프를 말한다. 각 칸의 간격은 일정하고, 높이는 어떤 정수로 주어진다. 위 그림의 경우 높이가 각각 2 1 4 5 1 3 3이다. � www.acmicpc.net 입력을 받을 때마다 stack의 top과 값을 비교해준다 1. top 입력값(height) 이전 사각형이 더이상 지속될 수 없는 상태이기 때문에 stack이 empty가 되거나 top 입력값(height) 이라 pop해줄 때 pop되는 이전 사각형의 시작 위치의 값을 가져와 현재 사각형의 시작 위치로 넣어주면 이렇게 최대 직사각형을 찾을 수 있다. #include #include #include using namespace std; int main()..

1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식�� www.acmicpc.net input과 stack의 top이 있을 때 1. 현재 input이 사칙연산인 경우 input의 우선순위 > top의 우선순위 라면 우선순위가 더 낮은 top을 계산해주면 안 되므로 우선순위가 더 높은 input을 stack에 push해준다. input의 우선순위 top의 우선순위가 될 때까지 pop해준 뒤 우선순위가 더 높은 상태가 된 input을 stack에 push해준다. 이때 top이 왼쪽 괄호일 수도 있는데 연산자 우선순위는 괄호 > 곱셈과 ..

5430번: AC 문제 선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다. 함수 R은 배열에 있 www.acmicpc.net 처음에 algorithm 라이브러리에 있는 reverse 함수를 썼었는데 시간 초과 걸려서 start 인덱스와 end 인덱스를 가지고 R과 D를 수행했다. R인 경우에는 start와 end를 교환해주고 D인 경우에는 배열이 비어있을 경우 error처리해주고 그 외엔 start가 그다음 숫자를 가리키게 하였다. 여기서 주의할 점은 입력으로 D 0 [] 가 들어오면 배열이 비어있는데 D를 사용하기 때문에 error를 출력해야 하지만 R 0 [] 이런 식으로 들..

3078번: 좋은 친구 문제 상근이는 환갑을 바라보던 나이에 수능 시험을 다시보고 교대에 입학했고, 초등학교 선생님으로 취직했다. 상근: 요즘 애들은 친구를 사귀지 않나봐. 내가 앞에서 보고 있으면, 친구가 있�� www.acmicpc.net 처음부터 끝까지 비교하면서 카운트하다 시간 초과 나서 여러 번 피 본 문제이다. 정렬도 하고 조건문 달아서 최소한으로 비교해줘도 시간 초과 밖에 안 나서 방법을 아예 다르게 해 보았다. 등수 1 2 3 4 5 6 이름의 길이 7 7 6 7 7 6 입력이 이런 상태이고 K는 3이라 가정할 때, 이름의 길이를 첫 index로 가지는 이차원 벡터를 정의해 준 뒤 입력을 받으면서 이름의 길이가 똑같은 아이들이 2명 이상일 경우(v[index].size>=2)에만 등수의 차..

1966번: 프린터 큐 문제 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료�� www.acmicpc.net 현재 문서의 중요도가 가장 클 경우에만 인쇄될 수 있는 조건이다. 1. M위치에 있는 문서가 몇 번째로 인쇄되었는지를 출력해야 하므로 큐에 pair로 중요도와 인덱스를 넣어준다. 2. 현재 문서의 중요도가 가장 큰지 판단해 주기 위해 중요도 배열을 따로 만들어 내림차순으로 정렬해준다. 3. 인쇄될 때마다 카운트 해주고 인쇄되는 문서가 M위치에 있을 때 카운트를 출력한다. #include #include #include #include using namespace..

2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 백준 계단 오르기 문제와 비슷하길래 비슷하게 풀려고 했다가 망해서 다른 풀이들 참고해서 풀었다. 시작 위치와 끝 위치는 어디든 상관이 없는 대신 3연속 마시기는 불가능하다. 현재 와인이 i번째에 있다고 할 때 그 위치가 세가지 경우로 나누어진다. 0번 연속인 경우 -> 0번이니까 현재 와인을 마시지 않는 것이므로 res[i-1] 1번 연속인 경우 -> 현재 와인을 마시고 그 전 와인은 마시지 않은 상태이다. 그리고 그 전 전 와인은 마시든 말든 상관이 없으므로 w..