https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 문제조건 배열에 자연수 x를 넣는다. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 우선 입/출력이 많이 일어나기 때문에 입출력에 대해서 시간을 줄여줘야한다. 다들 많이 알고 있는 단축 코드이다. ios::sync_with_stdio(false); cin.tie(0); https://dingcoding.tistory.com/62 ios::sync_with_st..

https://www.acmicpc.net/problem/22233 22233번: 가희와 키워드 1번째 글을 쓰고 난 후에, 메모장에 있는 키워드는 set, floyd, os가 됩니다. 2번째 글을 쓰고 난 후에, 메모장에 있는 키워드는 set, os가 됩니다. map은 1번째 글과 2번째 글에 중복으로 등장하였음을 www.acmicpc.net 문제조건 메모장에 키워드가 적혀있다.(중복X) 블로그에 글을쓰면 메모장에서 사라진다. 키워드가 , (쉼표)로 구분해서 주어진다. 블로그에 전부 글을 쓴뒤 메모장에 남은 키워드의 개수는? 키워드를 미리 map에 저장해두고, ","(콤마)를 만날때마다 단어를 만들어서 map에 있는 단어인지 체크만 하는 간단한 구현문제이다. #include #include #inclu..

https://www.acmicpc.net/problem/20310 20310번: 타노스 어느 날, 타노스는 0과 1로 이루어진 문자열 $S$를 보았다. 신기하게도, $S$가 포함하는 0의 개수와 $S$가 포함하는 1의 개수는 모두 짝수라고 한다. 갑자기 심술이 난 타노스는 $S$를 구성하는 문자 www.acmicpc.net 문제조건 0과 1로만 이루어진 문자열 S가 있음 0과 1의 개수가 각각 짝수개임 각각 절반의 개수를 제거했을때, 사전순으로 가장 빠른 문자열 구하기 1분만에,,? 풀었나,,? 이렇게 쉬운게 왜 정답률이 50%가 안되지 라고생각하며 풀었다. #include #include using namespace std; //S가 포함하는 0과 1의 개수 모두 짝수 //절반 제거후 사전순으로 가장..

https://www.acmicpc.net/problem/19637 19637번: IF문 좀 대신 써줘 첫 번째 줄에는 칭호의 개수 N (1 ≤ N ≤ 105)과 칭호를 출력해야 하는 캐릭터들의 개수 M (1 ≤ M ≤ 105)이 빈칸을 사이에 두고 주어진다. (1 ≤ N, M ≤ 105) 두 번째 줄부터 N개의 줄에 각 칭 www.acmicpc.net 문제조건 N개의 줄에 각 칭호의 이름과 칭호의 상한 값이 주어진다. 칭호는 전투력 상한값의 비내림차순으로 주어진다. M개의 줄에 걸쳐 캐릭터의 전투력에 맞는 칭호를 입력 순서대로 출력한다. 어떤 캐릭터의 전투력으로 출력할 수 있는 칭호가 여러 개인 경우 가장 먼저 입력된 칭호 하나만 출력한다. 처음 봤을때 너무 쉬워서 빠르게 구현부터했다. #include..

https://www.acmicpc.net/problem/2228 2228번: 구간 나누기 N(1 ≤ N ≤ 100)개의 수로 이루어진 1차원 배열이 있다. 이 배열에서 M(1 ≤ M ≤ ⌈(N/2)⌉)개의 구간을 선택해서, 구간에 속한 수들의 총 합이 최대가 되도록 하려 한다. 단, 다음의 조건들이 만족되 www.acmicpc.net 문제조건 각 구간은 한개이상의 연속된 수로 이뤄짐 서로다른 두 구간은 겹쳐있거나, 인접하면 안됨 정확히 M개의 구간이어야함 뭔가 좀처럼 접근방법이 떠오르지 않았다. 계속해서 경우의수가 다르기 때문에 DFS로 완전탐색을 돌려야하나 ,,? 어떻게 풀지 감이안와서 접근 방법만 찾아봤다. 역시 dynamic programming,,, 왠지 감이 안잡힌다 생각했다. 식을 세워야하는..

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 문제조건 (1,1) 에서 (n,m)까지 최단경로 벽을 하나까지 부술수있다. 조건 2 때문에 일반적인 bfs로 풀수가 없다. 벽은 부숴도 되고, 안부숴도되고 그렇다면 어떻게 하지,,? 생각을 해보면 bfs자체가 수행될때마다 최단거리를 의미하고, 그에따라 queue에 넣을 조건만 추가해주면 된다. 벽은 하나까지 부술수있으므로, 배열을 3차원배열로 만들어주고, queue에도 (..

https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 문제조건 각 탑의 높이에서 x축에 평행하게 왼쪽으로 레이저 빔을 발사한다. 제일 먼저 레이저를 맞은 탑에서 레이저 신호를 수신한다. 각각 탑에서 쏜 레이저를 어느 탑에서 수신하는가? 수신하는 탑이 없으면 0을 출력 문제는 정말 간단하다. 왼쪽으로 가다가 자신의 높이보다 높은 탑중에 가장 먼저 만나면 그 탑을 저장하면 된다. #include #include #include #define MAX 5..

https://www.acmicpc.net/problem/12919 12919번: A와 B 2 수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈 www.acmicpc.net 문제조건 A,B로만 이루어진 두 문자열 S, T 가 주어지고, S를 T로 바꾼다. 문자열뒤에 A를 추가한다. 문자열의 뒤에 B를 추가하고 문자열을 뒤집는다. S를 T로 바꿀수 있으면 1 출력, 아니면 0 출력 S에서 두가지 행동만 할 수 있는데 행동들이 전부 문자 길이를 늘리는 것이므로 S, T가 똑같은 길이가 되었을때, 같은 문자열이 아니라면 0을 출력하..

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 문제조건 수빈이와 동생이 있다. 걷는다 : X+1 or X-1 (1초) 순간이동 : 2 * X (0초) ☞ 시간 안걸림 수빈이가 동생을 찾는 가장 빠른시간? 문제를 보고 수빈이와 동생이 아닌, 출발지와 목적지로 생각을 바꿔봤다. 그러면 문제가 평소에 익숙하게 보던 최단거리 찾기가 된다. 그러나, 일반적인 최단거리 찾기와 다른 점은 순간이동을 할때는 시간이 안걸..

https://www.acmicpc.net/problem/2531 2531번: 회전 초밥첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤www.acmicpc.net문제조건 k개의 접시 연속해서 먹으면 정액할인 가격1번에 해당할때, 초밥 번호 쿠폰발행, 그 번호 공짜, 번호 없으면 새로 만들어줌손님이 먹을 수있는 초밥종류의 최댓값?가장 많이 먹을 수 있는 경우? 쿠폰발행된 것이 아닌 초밥들을 연속해서 먹는다. 뭔가 투포인터를 이용해서 풀어야만 할 것같았는데, 투포인터를 활용한  '슬라이딩 윈도우' 기법을 활용했다.거창해 보이..