je_record

문제 특정 도시에서 출발하여 도달할 수 있는 모든 도시 중에서 특정 최단 거리를 가지는 도시 번호를 출력한다. https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 조건 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재 모든 도로의 거리는 1 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력 출발 도시 X에..

문제 문자열 S는 태그와 단어를 포함한다. 이때 단어만 뒤집는다. https://www.acmicpc.net/problem/17413 17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net 조건 문자열 S 알파벳 소문자, 숫자, 공백(' '), 특수 문자('')로만 이루어진다. 시작과 끝은 공백이 아니다. ''가 문자열에 있는 경우 번갈아가면서 등장하며, '

문제 바둑판의 상태가 주어지면 흰색 또는 검은색 중 무슨색이 이겼는지 판단 https://www.acmicpc.net/problem/2615 2615번: 오목 오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호 www.acmicpc.net 조건 바둑판의 크기는 19 * 19 같은 색의 바둑알이 연속적으로 5알이 놓이면 이긴다. 6알 이상이 연속적으로 놓인 경우에는 이긴 것이 아니다! -> 놓치기 쉬움 입출력 입력 바둑판이 19 * 19로 숫자로 표시된다. 검은 바둑알: 1, 흰 바둑알: 2, 알이 놓이지 않는 자리: 0 출력 승부가 결정이 나는 경우 검정 바..

문제 원형으로 이루어진 마을의 집에는 돈이 있다. 인접한 두 집을 털면 경보가 울린다. 이 때, 도둑이 훔칠 수 있는 돈의 최댓값을 구한다. 접근 규칙을 한번에 찾기 힘든 문제라 배열의 길이를 늘리면서 생각해보았다. [1, 2] 집이 2개라면 당연히 돈이 더 많은 2를 선택 [1, 2, 3] 집이 3개라면 당연히 3 선택 [1, 2, 3, 4] 2와 4 선택 [1, 10, 20, 4, 40] 20과 40 선택 그렇다면 점화식은 어떻게 세워야 할까??? [1, 10, 20, 4, 40]을 자세히 살펴보면 최대한 큰 수를 고를 수 있는 모든 경우를 알아보기 위해, 각 위치에서 최대한 큰 값을 고를 수 있는 경우를 알아야 한다. 앞에서부터 각 위치에서 가장 큰 경우를 따져보자. 1: 가장 큰 경우는 당연히 자..

문제 집에서 학교까지 물이 잠긴 지역을 피해 가는 최단경로의 개수를 구한다. 접근 dp 배열을 통해 각 위치까지 가는데 드는 최단 경로의 개수를 저장한다. 모두 0으로 초기화한다. 먼저 집이 있는 행과 열은 해당 위치까지 가는 최단 경로가 직진하는 경우 단 1개 뿐이므로 1로 설정한다. 이때 주의할점은 집이 있는 행과 열에 웅덩이가 있는 경우는 해당 웅덩이 다음부터는 1로 설정을 멈추어야 한다!(웅덩이가 있으면 직진을 할 수 없으므로!!!) -> 이 부분을 고려안해서 맨 처음에 틀렸었다😕 나머지 위치에 대해서는 왼쪽과 위쪽의 최단 경로의 개수 값을 더하여 저장한다. 이 과정을 반복하면 학교가 있는 위치의 dp 값이 집에서 학교까지 물이 잠긴 지역을 피해 가는 최단 경로의 개수가 된다. 성공 코드(내 코드..

문제 삼각형의 꼭대기에서 바닥까지 대각선 방향/한 칸 오른쪽/한 칸 왼쪽으로 이동하며 거쳐간 숫자의 합이 가장 큰 경우를 찾아 해당 합을 반환한다. 접근 dp 배열을 통해 삼각형의 위에서 2번째 층부터 탐색하며 바로 위층에서 현재 위치로 올 수 있는 두 경로 중 숫자가 더 큰 것을 선택하여 현재 위치의 숫자와 합하여 저장한다. 이를 맨 아래층까지 반복하면 맨 아래층에서 가장 큰 값이 삼각형의 꼭대기에서 바닥까지 거쳐간 숫자의 합이 가장 큰 경우에 해당된다. 아래 예를 통해 직접 구해보자. 해당 예시의 경우 30을 반환하게 된다. 성공 코드(내 코드) #include #include #include using namespace std; int solution(vector triangle) { int ans..