생각하는 아져씨

9461번: 파도반 수열https://www.acmicpc.net/problem/9461 문제 정의오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오. 접근 방법규칙을 찾고 점화식을 세우는 다이나믹 프로그래밍을 이용한다. 문제 해설규칙을 찾으면 N=6부터 점화식을 세울 수 있다.dp[i] ..

https://school.programmers.co.kr/learn/courses/30/lessons/42895 문제 정의어떤 숫자 N과 numbers가 주어질 때, N과 사칙연산만 사용해서 numbers를 표현해야 한다.이 때 N 사용횟수의 최솟값을 리턴해야 한다. 접근 방법다이나믹 프로그래밍 문제임을 알고 있어서 dp 테이블을 어떻게 정의해야 하는지 고민하다가 처음에는 다음과 같이 정의했다.dp[i]: i를 만드는데 필요한 N의 최소 개수 N = 5일 때, dp[0] = 0, dp[1] = 5/5 → 2, … dp[5] = 1 그리고 점화식으로는, dp[i] = min(1~(i-1) 중 더해서 i가 되는 조합의 숫자에 해당하는 인덱스의 dp 값) 즉, dp[7] = min(dp[1] + dp[6],..

2805번: 나무 자르기https://www.acmicpc.net/problem/2805 문제 정의상근이는 M미터의 나무가 필요해서 나무를 벌목하려고 한다. 절단기의 높이를 설정하면, 높이만큼 나무를 잘라주는데, 나무들의 높이가 주어졌을 때 적어도 M미터의 나무를 가져가려면 절단기의 높이를 최대 몇까지 설정할 수 있을까? 접근 방법나이브한 접근방법나무리스트 [20, 15, 10, 17] 가 주어졌을 때, 절단기의 높이를 1~최대 나무 높이(=20)까지 설정해보면서, (나무-절단기높이)의 합이 M미터 이상인지 확인하면 된다.즉, sum(각 나무높이 - 절단기 높이) ≥ M (적어도 M 미터이므로, M이상과 비교하면 된다.)하지만, N은 최대 2,000,000,000 이므로, 이중 for문을 사용하면 시간 ..

10816번: 숫자 카드 2https://www.acmicpc.net/problem/10816 문제 정의상근이는 숫자 카드 N개를 가지고 있다. 정수가 M개 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하면 된다. 만약 상근이가 6 3 2 10 10 10 -10 -10 7 3 카드를 가지고 있을 때,10 9 -5 2 3 4 5 -10 → 이 숫자들을 몇개 씩 가지고 있는지 출력하면 된다.이 예에서는 10은 3개 가지고 있으므로 3으로 출력하면 된다. 접근 방법N과 M이 최대 500,000이 될 수 있는데, 일일히 2개의 리스트를 비교하기에는 O(N2)O(N^2)O(N2) 으로 시간 초과가 뜰 수 있다.그래서 x가 리스트 안에 몇 개 있는지 찾기 위해서 기준 숫자인 mid..

1018번: 체스판 다시 칠하기https://www.acmicpc.net/problem/1018 문제 정의M*N 크기의 보드에서 8*8 크기의 체스판을 만들려고 한다.체스판은 검은색/ 흰색이 번갈아 칠해져있어야 하는데, 보드는 그렇지 않다.보드를 8*8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해서 체스판을 만들 때, 칠해야 하는 최소 정사각형 개수를 구하면 된다. 접근 방법N과 M의 범위가 50보다 작거나 같다고 해서 모든 원소는 최대 2500개이고, 그 중에서도 8*8 크기의 체스판이면 64개로 4중 for문을 돌아도 시간 초과는 나지 않는다.따라서 완전 탐색으로 접근했다. 시작점이 되는 원소를 기준으로 8*8 크기의 체스판을 만들고, 그 체스판 원소 중 색칠을 다시 해야 하는 부분을..

https://school.programmers.co.kr/learn/courses/30/lessons/42839문제 정의문자열로 주어진 종이조각으로 만들 수 있는 소수가 몇 개인지 계산해야한다. 접근 방법문자열로 주어진 종이조각을 분리한 후 조합을 이용해 만들 수 있는 모든 숫자를 만든다.그 다음에 그 숫자가 소수인지 판단하면 된다.이 때 쓸 수 있는 유용한 함수에는 itertools의 permutations이 있다.문제 해설permutations의 인자로 들어갈 리스트를 만들어 주기 위해서 numbers를 분리했다. (numbers는 문자열로, 공백이 없이 주어졌기에 split() 함수를 사용할 수 없었다. 따라서 for문으로 일일히 분리했다.)permutations을 사용해 모든 조합을 구하고 jo..