메이쁘

https://www.acmicpc.net/problem/15831 15831번: 준표의 조약돌 첫 줄에 조약돌의 총 개수 N, 준표가 원하는 검은 조약돌의 최대개수 B와 하얀 조약돌의 최소개수 W가 주어진다. 둘째 줄에는 N개의 조약돌의 정보가 한 줄로 주어진다. i번째 문자가 B라면 i번 조 www.acmicpc.net 안녕하세요. 이 문제는 투포인터 문제로, 어느 회사 코딩테스트의 마지막 문제 유형과 비슷해서 끝나자마자 한번 풀어봤습니다.. 투포인터도 나올 줄 몰랐고, 실제로 코테 문제도 풀지 못했기에 아쉬워서 투포인터 다시 공부해야겠다 다잡고 시작했습니다만 결국 다른 사람들의 해설을 참고했습니다ㅠㅠ 알고리즘 풀이는 간단합니다. Input 이 10 1 2 WBBWWBWWBW 라고할 때, start ..

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 이 문제는 DFS 문제입니다. BFS를 사용하면 모든 경우(상하좌우 및 모든 경로)에 대해 분기처리되서 하나씩 비교해야하기때문에 아닌것 같고 DFS를 사용해서 맞는 경우에만 깊이있게 최대 경로를 탐색해내는게 맞는 것 같아서 DFS를 사용했습니다. 알고리즘은 간단해서, - 1행 1열부터 말 움직이기 시작. - 별도 목적지가 없고, 최대로 움직일 수 있는 칸을 구하는 문제기 때문에 DFS(맨 ..

https://www.acmicpc.net/problem/17612 17612번: 쇼핑몰 입력의 첫 줄에는 2개의 정수 N(1 ≤ N ≤ 100,000)과 k(1 ≤ k ≤ 100,000)가 주어진다. 다음 줄부터 N개의 줄에 걸쳐 고객 N명의 정보가 줄 맨 앞의 고객부터 맨 뒤 고객까지 순서대로 주어진다. i번째 www.acmicpc.net 안녕하세요. 이 문제는 로직이 바로 생각났지만, 예외 처리 하나가 걸려서 애먹었습니다. 바로 여기인데요. 같은 시간에 끝나는 계산대가 여러 개 있다면, 가장 번호가 작은 계산대부터 손님을 안내해야했습니다. 이를 고려하지 않았었기 때문에 같은 시간에 끝나는 계산대가 여러개였지만, 높은 번호의 계산대를 우선순위 큐에서 먼저 poll하기 때문에, 거기에 다음 고객을 넣고..

https://www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net 안녕하세요. 그리디 알고리즘을 활용한 문제로, 난이도는 쉬운 편입니다. 저는 처음에 간단하게 생각해서 1) 오름차순 정렬 2) 앞에서 두 장 카드 선택 3) 더해서 다시 두 장 카드 값에 대입 4) M번 1~3 반복 해서 맞추긴 했습니다만, 너무 효율성이 낮아서 다시 생각해봤고, 결국 삽입 정렬을 활용했습니다. 알고리즘 간단합니다. 1) 처음 입력받은 카드 배..

https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 안녕하세요. 처음에는 다익스트라? 했는데 사이클 그래프가 생기기 때문에 취소. 다시 보니 DP와 DFS를 사용하는거 같더라구요. DFS는 1) 한 번 방문한 도시는 다시 방문할 수 없고, 2) 어느 도시를 들려야 최소 비용이 될 지 판단해야하기 때문에, 3) N이 16 이하인 경우이기 때문에 사용했고, 3)의 경우에 좀 더 효율적으로 시간과 메모리를 줄이기 위..

www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 K - 1개를 0으로 만드는 이유는, 위 예시에서 [1, 3] 과 [6, 9] 두 구역을 나눴을 때, 3과 6 사이 간격은 고려하지 않습니다. 3과 6 사이가 3으로 모든 간격 값 중 가장 높은 값이었죠. 즉, 집중국을 놓을 때 두 센서를 하나의 구역에 포함시키지 않고 분리했으므로 두 센서 사이 간격은 무시됩니다. 이를 응용한다면, 가장 간격이 높은 값을 기준으로 분리시켜 구역을 만들면 최소합이 나오겠죠? 5) 모든 간격 값 더하기 이 때, 4)와 5)를 하나의 for문으로 수행할 수 있습니다. 즉, 간격 배열을 오름차순 정렬헀을 때, index 0부터 시작해서 N - K개를 순환하면 됩니다! 이상입니다...

www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 안녕하세요. 해당 문제는 DP(동적 프로그래밍) 관련 문제입니다. 문제 해결법은 간단합니다. ========================== ㅇㅁ ㅁㅇ ㅇㅁ ㅁㅇ ㅁㅁ ㅁㅁ ㅁㅇ ㅇㅁ ㅁㅁ ㅁㅁ ㅁㅁ ㅁㅁ ㅇㅁ ㅁㅇ ㅁㅇ ㅇㅁ ㅇㅁ ㅁㅇ ========================== * ㅇ : 성공 ㅁ: 식대 위와 같은 경우, i = 3인 경우에도, N번째 줄에는 총 3가지(양쪽 칸에 사자를 넣지 않음, 왼쪽칸에만 사자를 넣음, 오른쪽칸에만 사자를 넣음) 존재힙니디. 점화식 도출 1) 양쪽 : dp[k][0] = dp[k-1][0] + dp[..

www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 안녕하세요. 다익스트라 알고리즘 문제 리뷰합니다. 해당 문제는 어렵지 않았습니다! 단, 저도 헷갈렸던 부분이 있습니다. 밑줄 친 부분에서, 수색 범위 값은 m , 길의 개수는 r 입니다!!! (조건 값을 r로 했다가 왜틀렸는지 몰랐...) 바로 솔루션 설명하겠습니다. 솔루션 - 우선, 양방향 그래프입니다. - 다익스트라 결과값 배열은 시작 지점부터 해당 지점까지 이동하는 최소 거리 입니다. - 그럼 결과값 배열을 어..

www.acmicpc.net/problem/10610 10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한 www.acmicpc.net 안녕하세요. 문자열 문제입니다. 난이도는 보통이에용! 가장 먼저, 30의 배수가 되는 조건을 생각해봤습니다. 1) 맨 뒤가 0이 있어야 함(뒤에 0의 개수는 상관X) 2) 3의 배수 그럼, 이 30의 배수를 찾는 문제를 해결하는 매커니즘을 작성해보겠습니다. 매커니즘 1) 0을 전부 제외(어차피 맨 오른쪽에 붙이면 되니까) 2) 0을 제외한 남은 숫자들을 전부 더했을 때, 값이 3의 배수인지 확인하기 -> 아니면 ..

www.acmicpc.net/problem/2917 2917번: 늑대 사냥꾼 첫째 줄에 N과 M (1 ≤ N, M ≤ 500)이 주어진다. 둘째 줄부터 N개 줄에는 숲의 지도가 주어진다. 지도에 'V'와 'J'는 딱 하나만 있고, 적어도 하나의 '+'가 있다. www.acmicpc.net 안녕하세요. 처음에 DFS로 풀었다가 시간 초과가 발생했습니다. 그래서 여러 방법을 찾다가 BFS를 깨달았습니다. 로직은 간단합니다. 1) 나무 클래스를 만듭니다. x, y, distance int 변수가 포함되어 있습니다. 2) 맵에서 나무들의 위치를 담은 클래스 객체를 별도의 큐에 저장합니다. 이 때, 미리 거리를 담는 맵(int 2차원 배열) 에 해당 나무의 위치 초기값을 0으로 세팅합니다. *** 나무가 아닌 지..