Jubil의 프로그래밍 블로그

감사합니다(한국 아시안게임 축구 금메달!)

2167_2차원 배열의 합 링크 https://www.acmicpc.net/problem/2167 풀이 DP[i][j] (1

작년에 같은 팀으로 힘겹게 본선 올라와서 6등까지 상인데 7등을 했었다.그 때는 정말 아쉬웠다ㅜㅜ 올해는 이렇게 상을 탈 수 있어서 만족스럽다. (물론 조금 더 집중했다면 은상까지 노려볼 수 있지 않았나 싶다!)

9465_스티커 링크 https://www.acmicpc.net/problem/9465 풀이 만약 별에서 시작했다면 1이나 2를 갈 수 있습니다. 하지만 2는 1을 거쳤다 갈 수 있기 때문에 1로 가야합니다. 이 상황도 마찬가지로 1로 가는 게 이득입니다. 그렇다면 위에서 시작했던 밑에서 시작했던 대각선으로만 가는 게 최선의 방법일까요? 아닙니다. 반례를 들어보면, 이렇게 대각선으로만 가면 102라는 값이 나오지만 최적이 아니라는 것을 알 수 있습니다. 이렇게 두 칸 전에서 오는 값도 체크해줘야 합니다. 세 칸 전에서 오는 건 충분히 더 많은 구역을 거칠 수 있기 때문에 보지 않아도 됩니다. DP[n][i]를 n번째 줄의 i번째까지 얻을 수 있는 최고의 점수라고 정의합니다. (n은 0~1, i는 1~10..

1149_RGB거리 링크 https://www.acmicpc.net/problem/1149 풀이 집 i의 이웃은 집 i-1과 i+1이고, 이웃은 같은 색으로 칠할 수 없습니다. DP[i][j] (집 i를 j색으로 칠했을 때까지의 최소 비용, j = 0 R, 1 G, 2 B) cost[i][j] (집 i를 j색으로 칠할 때의 비용, j = 0 R, 1 G, 2 B) 이라고 정의하겠습니다. 그렇다면 DP[i][0]은 이웃은 같은 색을 칠할 수 없다는 조건에 의해, min(DP[i-1][1], DP[i-1][2]) + cost[i][0]로 정의됩니다. (전에 다른 색 G, B로 칠했을 때까지의 최소 비용 + 현재 R로 칠했을 때의 비용) 즉, 나머지 색들도 생각해보면 다음과 같은 식이 나옵니다. DP[i][0..

1764_듣보잡 링크 https://www.acmicpc.net/problem/1764 풀이 STL의 map을 사용하면 python의 dictionary처럼 사용할 수 있습니다. 듣보잡 문제처럼 문자열을 인덱스로 사용해야 할 때, 아주 유용하게 사용할 수 있습니다. map mp 로 선언을 했다면, mp.first가 string을, mp.second가 int를 가리킵니다. 그리고 배열처럼 mp[mp.first]으로 mp.second에 접근할 수 있습니다. 코드

2075_N번째 큰 수 링크 https://www.acmicpc.net/problem/2075 풀이 오름차순 priority_queue를 이용해서 정렬해주면 됩니다. 코드

10799_쇠막대기 링크 https://www.acmicpc.net/problem/10799 풀이 이 문제는 Stack을 사용해서 풀 수 있습니다. 일단 쇠막대기의 오른쪽 끝과 레이저를 구분해서 두 가지의 경우로 나누어 풀면 됩니다. 여는 괄호가 들어온다면 스택에 push하고 닫는 괄호가 들어온다면 pop을 해줍니다. 닫는 괄호가 들어왔을 때는 전의 괄호가 여는 괄호인지 닫는 괄호인지 확인합니다. 여는 괄호라면 레이저이기 때문에, 현재 쇠막대기만큼 즉, stack의 size만큼 더해주면 됩니다. 닫는 괄호라면 쇠막대기의 오른쪽 끝이기 때문에, 1을 더해주면 됩니다. 두 번째 예제를 실제로 그려서 계산해보면 이렇게 됩니다. 코드

9012_괄호 링크 https://www.acmicpc.net/problem/9012 풀이 괄호 문제는 Stack으로 구현할 수 있습니다. 여는 괄호를 push, 닫는 괄호를 pop이라고 생각해줍니다. pop을 하기 전에 empty 체크를 해서 비어 있는데 pop을 했다면 잘못된 괄호 문자열이라고 체크해줍니다. 그리고 마지막에 괄호 문자열이 끝나고 스택의 empty 여부를 체크했을 때 안에 data가 있다면 괄호가 다 닫힌 게 아니므로 잘못된 괄호 문자열이라고 체크해줍니다. 1. empty인데 pop 시도할 경우 2. 끝났는데 empty가 아닐 경우 코드

10845_큐 링크 https://www.acmicpc.net/problem/10845 풀이 하나하나 사용해주면 됩니다. 코드 주석으로 설명하겠습니다. 코드