두치의 개발공부

문제 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이 피보나치 수열의 형태를 보이고 있다. 이를 점화식으..