je_record

문제 문자열 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..

문제 숫자 N을 사칙연산을 통해 number로 표현할 때 사용되는 N의 최소 사용횟수를 구한다. 접근 규칙을 찾아서 dp 배열을 만들어 적용시키고자 하였으나 무엇을 기준으로 규칙을 찾아야 할 지 감이 잡히지 않아 문제에서 구하고자 하는 것을 다시 살펴보았다. N의 최소 사용횟수를 구한다는 점에서, N을 1개, 2개, 3개 ... 사용해서 만들 수 있는 수들을 직접 적어보았다. 다음 예시를 통해 살펴보자. N number return 2 11 3 dp[cnt]: N을 cnt 개수 만큼 사용하여 만들 수 있는 수 dp[1] - 2 dp[2] - 22 dp[1]과 dp[1]로 사칙연산 - 2+2=4 - 2-2=0 - 2*2=4 - 2/2=1 dp[3] - 222 dp[1]과 dp[2]로 사칙연산 - 2와 22..