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번에 해당할때, 초밥 번호 쿠폰발행, 그 번호 공짜, 번호 없으면 새로 만들어줌손님이 먹을 수있는 초밥종류의 최댓값?가장 많이 먹을 수 있는 경우? 쿠폰발행된 것이 아닌 초밥들을 연속해서 먹는다. 뭔가 투포인터를 이용해서 풀어야만 할 것같았는데, 투포인터를 활용한  '슬라이딩 윈도우' 기법을 활용했다.거창해 보이..

https://www.acmicpc.net/problem/20922 20922번: 겹치는 건 싫어홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열www.acmicpc.net문제조건같은 원소 k개 이하최장 연속 부분 수열의 길이처음보는 문제유형이라 많이 당황했다,,dp, LCS 등등 알고리즘을 고민해봤지만, 도저히 풀리는 그림이 나오지 않았다.따라서 투 포인터라는 접근방식이 필요했다. https://khu98.tistory.com/187 [백준OJ] 20922번 겹치는 건 싫어https://www.acmicpc.net/problem/20922 20922번: 겹치는 건..

https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 문제조건 목표지점부터 모든 지점에 대해서 목표지점까지의 거리 구하기 너무 당연하게 BFS로 풀이를 시작했다. #include #include using namespace std; int n, m, map[1001][1001], visited[1001][1001], dist[1001][1001]; int dy[] = { -1, 0, 1, 0 }; int ..

https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net 문제조건 몸무게 : x, 키 : y → (x, y) x, y 둘다 커야 덩치가 더 크다고 한다. 각 사람의 덩치 등수를 매긴다 이 문제는 진짜 너무 쉽다,,,, 그냥 완전 탐색 문제였다. 한명씩 전부 비교해보면서 각각 등수를 출력하기만 하면된다,,! #include #include int n; using namespace std; vector v; int main(){ cin >> n..

https://www.acmicpc.net/problem/8979 8979번: 올림픽 입력의 첫 줄은 국가의 수 N(1 ≤ N ≤ 1,000)과 등수를 알고 싶은 국가 K(1 ≤ K ≤ N)가 빈칸을 사이에 두고 주어진다. 각 국가는 1부터 N 사이의 정수로 표현된다. 이후 N개의 각 줄에는 차례대로 각 www.acmicpc.net 문제를 보자마자 딱 느꼈다. 쉬운 문젠데 if문 잘 걸어 줘야겠다,,,, 특정 나라의 순위를 구하는 거여서 그냥 배열로 전부 나타내 주었다. #include #include #include using namespace std; int gold[1001], silver[1001], bronze[1001]; int n, k; int main() { cin >> n >> k; fo..