![]()
📖 문제 16395번: 파스칼의 삼각형 파스칼의 삼각형은 이항계수를 삼각형 형태로 배열한 것인데, 블레즈 파스칼(1623-1662)을 따라 이름 붙여졌다. 단순한 형태로, 파스칼의 삼각형은 다음과 같은 방법으로 만들 수 있다. N번째 행 www.acmicpc.net 💡 풀이 방식 • DP . 2차원 배열을조합 식 nCr = n-1Cr-1 + n-1Cr 을 활용해 채운다. - 첫 번째 열에 있는 칸과, 행=열인 칸은 1로 초기화 dp[n][k] = dp[n-1][k-1] + dp[n-1][k] 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 import java.util.*; import java.io.*; publi..
![]()
📖 문제 2167번: 2차원 배열의 합 첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 www.acmicpc.net 💡 풀이 방식 • (i,j) ~ (x,y) 구간에 대한 누적합을 구한다. 1) 초기 2차원 누적합 행렬은 다음과 같이 채운다. dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + arr[i][j]; 2) 부분 행렬의 값은 다음과 같이 구한다. dp[x][y] - dp[x][j - 1] - dp[i - 1][y] + dp[i - 1][j - 1] 💥 유의사항 dp[N][M..
![]()
📖 문제 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 💡 풀이 방식 • DP dp 배열을 만든다. (dp[i][j] : 해당 칸 (i, j)까지 스티커를 떼었을 때 얻을 수 있는 최대 점수) 2. 0번 열은 본인이 최대이므로 본인으로 초기화한다. 3. 1번 열은 특수처리한다. [0][1]은 왼쪽 아래 값과 본인 칸 값 더하기 [1][1]은 왼쪽 위쪽 값과 본인 칸 값 더하기 dp[0][1] = dp[1][0] + arr[0][1]; dp[1][1] = dp[0][0] + arr[1][1]; 4...
![]()
📖 문제 17626번: Four Squares라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1www.acmicpc.net 💡 풀이 방식• DP규칙을 찾아 점화식을 채운다.1 : 1^2 ⇒ 1개2 : 1^2 + 1^2 ⇒ 2개3 : 1^2 + 1^2 + 1^2 ⇒ 3개4 : 2^2 ⇒ 1개5 : 2^2 ..
![]()
📖 문제 20164번: 홀수 홀릭 호석호석이는 짝수랑 홀수 중에서 이니셜이 같은 홀수를 더 좋아한다. 운전을 하던 호석이는 앞차의 번호판이 홀수로 가득할 때 사랑스러움을 느낄 정도이다. 전화번호도 홀수만 있고 싶다. 그렇게www.acmicpc.net 💡 풀이 방식• 재귀, 브루트포스재귀 함수의 인자로 (현재 숫자, 여태껏 나온 홀수의 갯수)를 갖는다. [1] 재귀 함수 cut(int num, int total)1. 한 자리 숫자인 경우, 여지껏 나온 홀수의 갯수와 최솟값 최댓값을 비교해 갱신한다.2. 두 자리 숫자인 경우, 두 숫자를 분해한다. (재귀 함수 사용)3. 세 자리 이상의 숫자인 경우, 완전탐색을 통해 해당 숫자를 3등분할 인덱스 2개를 구한다.그리고 나서 해당 인덱스들에서 잘랐을 때..
![]()
📖 문제 10994번: 별 찍기 - 19예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요.www.acmicpc.net 💡 풀이 방식• 재귀. 재귀함수의 인자로는 (시작 행 위치, 가로줄 길이)를 가져간다. . 반복문을 통해 시작 위치부터 가로줄 길이까지 사각형 위치에 있는 칸을 별로 채운다. (맨 위 가로줄, 맨 아래 가로줄, 왼쪽 세로줄, 오른쪽 세로줄). 반복문이 끝나면, 시작하는 행의 위치는 2 더하고, 가로줄의 길이는 2씩 줄여 재귀함수를 돌린다. (그래야 안쪽에 줄어든 길이만큼 별을 생성할 수 있다.) 🔺 코드12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849import ..
![]()
📖 문제 17276번: 배열 돌리기각 테스트 케이스에 대해 회전 연산을 마친 후 배열의 상태를 출력한다. n줄에 걸쳐 각 줄에 n개의 정수를 공백으로 구분하여 출력한다. www.acmicpc.net 💡 풀이 방식• 구현 지문에서 알려준대로 그대로 구현하면 되더라,,, 1. 주대각선 \ (i, i)을 가운데 열 - (i, n / 2)로 옮긴다.2. 가운데 열 | (i, n /2)을 부대각선 / (n - i, i)으로 옮긴다.3. 부대각선 / (n - i, i)을 가운데 행 - (n/2, i)으로 옮긴다.4. 가운데 행 - (n/2, i)을 주대각선 \ (i, i)으로 옮긴다. 🔺 코드12345678910111213141516171819202122232425262728293031323334353..
![]()
📖 문제 ')로만 이루어져 " data-og-host="www.acmicpc.net" data-og-source-url="https://www.acmicpc.net/problem/17413" data-og-url="https://www.acmicpc.net/problem/17413" data-og-image="https://scrap.kakaocdn.net/dn/sIGT7/hyU5PVkXHF/evdmY3jb9h5rzxZFgoq3Q0/img.png?width=2834&height=1480&face=0_0_2834_1480"> 17413번: 단어 뒤집기 2문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자..
![]()
📖 문제 1244번: 스위치 켜고 끄기첫째 줄에는 스위치 개수가 주어진다. 스위치 개수는 100 이하인 양의 정수이다. 둘째 줄에는 각 스위치의 상태가 주어진다. 켜져 있으면 1, 꺼져있으면 0이라고 표시하고 사이에 빈칸이 하나씩www.acmicpc.net 💡 풀이 방식• 구현, 시뮬레이션👨 남자인 경우스위치 배열 switches 에서 인덱스가 입력받은 수의 배수인 칸의 상태를 변경한다. 👩 여자인 경우현재 칸은 무조건 상태를 변경한다.현재 칸의 왼쪽 위치 l과 현재 칸의 오른쪽 위치 r을 잡는다. (투 포인터)l과 r이 배열의 크기를 벗어나지 않는 동안 반복문을 수행한다. (while문 사용)만약 좌우 두 칸이 대칭인 경우 (swithces[l] == switches[r]), 좌우 두 칸을..
