Still Young

Level Bronze 문제 링크 [백준] https://www.acmicpc.net/problem/21820 [USACO] http://www.usaco.org/index.php?page=viewproblem2&cpid=1131 문제 요약 \(c\)배열의 일부 요소에 총 L을 더했을 때, 값이 h 이상인 요소가 h개 이상이라는 조건을 만족시키는 h의 최댓값 구하기 [내 풀이] 해결 방법 우선 \(c\)배열의 각 요소의 값이 몇 개씩 있는지를 저장하는 배열 \(d\)를 만든다. 이후에 \(d\)배열의 처음부터 끝까지 순회하며 문제에서 요구하는 대로 \(max_{i=0}^n(min(i,\sum_{i}^{n}d[i]))\) 를 구한다. 이 문제에서 한 가지 challenge가 있다면 L만큼 요소의 수를 더할..

Level Bronze 문제 링크 [백준] https://www.acmicpc.net/problem/23880 [USACO] http://www.usaco.org/index.php?page=viewproblem2&cpid=1157 문제 요약 board에서 .은 갈 수 있는 길, H은 지나갈 수 없는 길이라고 할 때, 좌상단에서 우하단으로 가는 경로의 수 이때, 오른쪽으로 혹은 아래로만 갈 수 있는데 최대 k번 방향을 바꿀 수 있다. [내 풀이] 해결 방법 전형적인 경로의 방법 수를 찾는 dp문제라고 생각했다. dp[i][j][d]는 (i,j)으로 이동할 때 도달할 수 있는 경우의 수이다. d의 값은 0과 1인데 각각은 처음에 오른쪽으로 이동하는 경우와 아래로 이동하는 경우를 나타낸다. board[i][j..

Level Bronze 문제 링크 [백준] https://www.acmicpc.net/problem/23879 [USACO] http://www.usaco.org/index.php?page=viewproblem2&cpid=1156 문제 요약 배열의 연속된 요소들의 값을 한번 올리거나 내리는 경우를 연산 1번으로 볼 때, \(t\) 배열을 \(p\) 배열과 동일하게 만드는데 필요한 최소 연산 횟수 구하기 [내 풀이] 해결 방법 우선 \(d[i]=t[i]-p[i]\)를 통해 \(p\) 배열과 \(t\) 배열의 차이를 배열에 저장한다. 값을 올리거나 내리는 것보다 연속된 요소들의 값을 한 번에 올리거나 내리는 경우가 더 효율적이다. 하지만, 어떤 방식으로 범위를 설정할지가 문제이다. \(d[a]>0\), \(..

Level Bronze 문제 링크 [백준] https://www.acmicpc.net/problem/23878 [USACO] http://www.usaco.org/index.php?page=viewproblem2&cpid=1155 문제 요약 G와 H로 이루어진 문자열에서 길이가 3 이상이고 G 또는 H가 단 하나만 포함된 부분 문자열의 개수를 구하는 문제 [내 풀이] 해결 방법 G와 H로 이루어진 문자열은 길이가 1 이상이고 G 또는 H가 연속되는 부분 문자열이 일렬로 이어지는 형태로 이루어져 있다(e.g. GGGG, H). 우선 문자열의 가장 왼쪽부터 오른쪽으로 연속되는 G와 H의 길이를 배열에 저장한다. 예를 들어, GGGGH의 경우 배열에 4와 1이 저장되는 것이다. 배열에 저장된 값이 하나뿐일 경..