두치의 개발공부

문제 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 문제풀이 매 순간 최적의 방법을 찾아내는 탐욕 알고리즘의 문제이다. 최소의 동전으로 가치의 값을 충족시켜야 하기 때문에 가치를 가장 큰 동전으로 많이 채워야 동전을 적게 쓸 수 있다. 오름차순으로 입력받는 동전을 내림차순으로 정렬하여 앞에서 부터 가치가 동전으로 나누어지는 값이면 몫은 사용된 동전 갯수로, 나머지값은 앞으로 채워..

문제 https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제풀이 탐욕 알고리즘을 적용하여 풀면 문제를 해결 할 수 있다. 지금 당장 시간이 가장 적게 걸리는 사람의 순서를 앞으로 하여 기다리는 시간을 최소화 하면 총 걸리는 시간을 최소화 할 수 있다. 처음에 문제를 풀 때는 각각의 사람이 기다린 시간과 소요되는 시간을 배열에 넣어서 제일 마지막에 더하는 방법으로 풀었고, 두번째에는 다른 사람들이 푼 풀이를 보니 이중 for문으로 간략하게 풀었길래 좀 더 좋은 풀이인 거 같아 ..

문제 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 문제 풀이 배열을 피라미드 형식으로 그려서 확인 하면 훨씬 보기 편하다. 위에서 아래로 내려오면서 숫자를 더하는 방향보다는, 아래에서 위의 어떤 숫자와 더할 것인지 선택하는 방향으로 생각하면 좀 더 쉽게 접근 할 수 있다. 7 -1 3 8 -2 8 1 0 -3 3번째의 8은 2번째의 3과 더할 수 밖에 없다. 3번째의 0은 2번째의 8과 더할 수 밖에 없다. 3번째의 1은 2번째의 3과 8 중에서 큰 값을 더하면 된다. 이를 점화식으로 나타내면 아래와 같다. j ..

문제 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 풀이 문제 조건이 3가지나 있어 복잡 해 보이지만, 결국에는 인접한 집의 경우에는 무조건 다른 색으로 칠해야 한다는 것 이다. 전에 집이 빨간색이면, 다음 집은 초록/파랑 전에 집이 초록색이면, 다음 집은 빨강/파랑 전에 집이 파란색이면, 다음 집은 빨강/초록 이다. 2가지 색깔 중 적은 비용을 선택하여 설치하면 된다. 첫번째 집을 빨,초,파 로 선택하였을 때를 가..

문제 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 문제 풀이 N은1 부터 차근차근히 그림을 그려나가 보면 점화식을 금방 발견할 수 있다. N 1 2 3 4 5 6 7 정삼각형 변의 길이 1 1 1 2 2 3 4 점화식 : dp[n] = dp[i-1] + dp[i-5] 초기값 : dp[1] = 1, dp[2] = 1, dp[3] = 1, dp[4] = 2, dp[5] = 2 코드 const answer = ([...number]) => { cons..

문제 https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 문제풀이 짖궂은 동주 때문에 0을 낱개로 사용할 수 없게 되었다... (1와 00 만 사용가능) N이 1 일 때부터 경우의 수를 보면 금방 규칙을 파악할 수 있다. N = 1 일 때 , 1 => 1개 N = 2 일 때, 11 / 00 => 2개 N = 3 일 때, 100 / 001 / 111 => 3개 N = 4 일 때, 1111 / 1001 / 0000 / 0011 / 1100 => 5개 N =..

문제 https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 문제풀이 0,1 이 각각 몇번씩 호출되는지 2가지의 경우로 나누어 생각하여 풀었다. N = 0일 때는 0이 1번, 1이 0번 N = 1일 때는 0이 0번, 1이 1번 N = 2일 때는 0이 1번, 1이 1번 N = 3일 때는 0이 1번, 1이 2번 N = 4일 때는 0이 2번, 1이 3번 N = 5일 때는 0이 3번, 1이 5번 0이 반복되는 횟수는 1,0,1,1,2,3... 1이 반복되는 횟수는 0,1,1,2,3,5... 각각 0,1이 피보나치 수열의 형태를 보이고 있다. 이를 점화식으..