목록분류 전체보기 (96)

키베이루's diary

[C++] 백준 1932번 정수 삼각형

1) 문제설명 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 2) 아이디어 삼각형에서 DP [줄][몇 번째 숫자] = 합의 최대로 설정하고 0으로 초기화한다. 반복문을 2개 돌려서 DP의 최댓값을 체크한다. 3) 코드 #include #include #include #include #include #include #include #include using namespace std; long long dp[501][501]={0,}; int main() { int n; long long arr[501][501]; c..
알고리즘/DP 2022. 6. 3. 12:46
[C++] 백준 1149번 RGB거리

1) 문제설명 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 2) 아이디어 DP를 이중 배열로 선언한다. DP [1][X] 에는 RED를 DP [2][X]에는 GREEN을 DP [3][X]에는 BLUE를 선택했을 경우로 나눈다. DP [1][X]에서는 DP [2][X-1] or DP [3][X-1]에 RED를 더했을 때의 최솟값을 DP [2][X]에서는 DP [3][X-1] or DP [1][X-1]에 GREEN를 더했을..
알고리즘/DP 2022. 6. 3. 06:05
[C++] 백준 2156번 포도주 시식

1) 문제설명 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 2) 아이디어 포도잔이 1개, 2개, 3개, 4개일때 될 수 있는 경우의 수를 하나씩 생각했다. 1개일때 : ( _ ) 2개일때 : ( _ ) ( _ ) 3개일때 : ( _ ) ( _ ) _ || ( _ ) _ ( _ ) || _ ( _ ) ( _ ) 4개일때 : ( _ ) ( _ ) _ ( _ ) || ( _ ) _ ( _ ) ( _ ) || _ _ ( _ ) ( _ ) 1개일때와 ..
알고리즘/DP 2022. 6. 2. 11:40
[C++] 백준 10844번 쉬운 계단 수

1) 문제설명 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 2) 아이디어 dp를 이중배열로 받아서 (i / j) 의 인덱스를 각각 (자릿수 / 마지막 수) 로 생각한다. 마지막수/ 자릿수 0 1 2 3 4 5 6 7 8 9 1 0 1 1 1 1 1 1 1 1 1 2 1 1 2 2 2 2 2 2 2 1 3 1 3 3 4 4 4 4 4 3 2 4 3 4 7 7 8 8 8 7 6 3 마지막 수가 0 일때와 9일때를 제외한 나머지는 dp[자릿수][마지막수] = dp[자릿수-1][마지막수-1] + dp[자릿수-1][마지막수+1] 인 것을 알 수있다. 3) 코드 #..
알고리즘/DP 2022. 6. 2. 09:36
[C++] 백준 1449번 수리공 항승

1) 문제설명 https://www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 www.acmicpc.net 2) 아이디어 입력받은 배열을 오름차순으로 정렬하고 앞에서 뒤를 뺀 결과만큼 테이프를 소모한다. 그리고 테이프를 모두 소모하면(테이프의 길이가 1보다 작을 경우) 테이프를 다시 리셋시켜준다. 3) 코드 #include #include #include #include #include #include #include #include using namespace std; ..
알고리즘/Greedy 2022. 5. 31. 23:29
[C++] 백준 2847번 게임을 만든 동준이

1) 문제설명 https://www.acmicpc.net/problem/2847 2847번: 게임을 만든 동준이 학교에서 그래픽스 수업을 들은 동준이는 수업시간에 들은 내용을 바탕으로 스마트폰 게임을 만들었다. 게임에는 총 N개의 레벨이 있고, 각 레벨을 클리어할 때 마다 점수가 주어진다. 플레이어 www.acmicpc.net 2) 해결방법 반복문을 2개 이용하여 입력받은 배열이 오름차순이 될 때까지 뒤에서부터 1씩 빼주고 그 과정을 진행할 때마다 카운트를 +1씩 늘려준다. 이후 카운트를 출력한다. 3) 코드 #include #include #include #include #include #include #include #include using namespace std; long long dp[1000..
알고리즘/Greedy 2022. 5. 31. 05:09
[C++] 백준 18870번 좌표압축

1) 문제설명 https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 2) 해결방법 2개의 벡터에 인덱스와 값을 저장해서 값을 변환 한 뒤 인덱스에 맞게 다시 정렬하는 방법을 사용했다. pair를 사용하여 두 개의 벡터 (v1, v2)를 선언, v1의 값을 오름차순으로 정렬한다. 오름차순으로 정렬한 v1에서 첫 번째 값과 두 번째 값이 같다면 같은 순위이고 두번째 값이 더 크다면 순위가 +1 되기 때문..
알고리즘/기타 2022. 5. 26. 16:42
[C++] 백준 10610번 30

1) 문제설명 https://www.acmicpc.net/problem/10610 10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한 www.acmicpc.net 2) 해결방법 입력을 하나씩 char형으로 받은 후에 int 형으로 변환한다. 그 후 입력받은 값의 합을 저장한 후에 내림차순으로 정렬한다. 입력받은 값의 합이 3의 배수이면 내림차순으로 출력하고 3의 배수가 아니면 -1을 출력한다. 3) 코드 #include #include #include #include #include #include #include #include using n..
알고리즘/기타 2022. 5. 26. 03:36
Prev 1 ··· 8 9 10 11 12 Next