거의 알고리즘 일기장

https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수� www.acmicpc.net 풀이방법 dp문제이며 직전에 푼 쉬운 오르막과 거의 유사한 문제다. 그냥 똑같다고 보면됨. 그러므로 생략하겠습니다.ㅎ 전체코드 #include #include #define DIV_NUM 10007 using namespace std; long long dp[10][1001]; int N; void dpInit() { for (int i = 0; i

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 주의사항 %를 계산시마다 할것!!! 전체코드 재귀 풀이 #include #define DIV_NUM 1000000000 using namespace std; long long dp[10][101]; int N; void dpInit() { for (int i = 0; i n; long long int result = 0; for (int j = 1; j

https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 www.acmicpc.net 풀이방법 제곱수를 미리 구해놓음 void powNumberInit() { powNumber[1] = true; for (int i = ..

https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다. www.acmicpc.net 풀이방법 메모제이션 문제, 거의 동일한 방식으로 푼 밑의 풀이를 참고. https://kunkunwoo.tistory.com/100 백준 2293번 _ 동전 1 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는..

https://www.acmicpc.net/problem/9465 9465번: 스티커 문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다. 모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점 www.acmicpc.net 풀이방법 선택의 경우가 3가지가 있다. 위의 경우들을 끝까지 갈때까지 반복하면됨. 전체코드 #include #include using na..

https://www.algospot.com/judge/problem/read/LIS algospot.com :: LIS Longest Increasing Sequence 문제 정보 문제 어떤 정수 수열에서 0개 이상의 숫자를 지우면 이 수열의 부분 수열 (subsequence) 를 얻을 수 있다. 예를 들어 10 7 4 9 의 부분 수열에는 7 4 9, 10 4, 10 9 등이 있다. 단, 10 4 7 은 원래 수열의 순서와 다르므로 10 7 4 9 의 부분 수열이 아니다. 어떤 부분 수열이 순증가할 때 이 부분 수열을 증가 부분 수열 (increasing subseque www.algospot.com O(n^2) 풀이 반복문 풀이 #include #include using namespace std; ..

https://algospot.com/judge/problem/read/TRIANGLEPATH algospot.com :: TRIANGLEPATH 삼각형 위의 최대 경로 문제 정보 문제 6 1 2 3 7 4 9 4 1 7 2 7 5 9 4 위 형태와 같이 삼각형 모양으로 배치된 자연수들이 있습니다. 맨 위의 숫자에서 시작해, 한 번에 한 칸씩 아래로 내려가 맨 아래 줄로 내려가는 경로를 만들려고 합니다. 경로는 아래 줄로 내려갈 때마다 바로 아래 숫자, 혹은 오른쪽 아래 숫자로 내려갈 수 있습니다. 이 때 모든 경로 중 포함된 숫자의 최대 합을 찾는 프로그램을 작성하세요. 입력 입력의 첫 줄에는 테 algospot.com 접근 시간 : 5초, 테스트케이스 : 최대 50개, n : 최대 100 딱봐도 이 ..

https://codeforces.com/problemset/problem/455/A Problem - 455A - Codeforces codeforces.com 풀이방법 ak를 선택시 ak-1, ak+1은 선택 못한다는것을 유의해서 점화식을 짜야한다. dp[i] = max( dp[i-1], dp[i-2] + cnt[i]+i ) 전체코드 #include #include using namespace std; int n; long long cnt[100002]; long long dp[100002]; void Input() { cin >> n; int value; for (int i = 0; i > value; cnt[value]++; } } int main() { Input(..

https://codeforces.com/problemset/problem/230/B Problem - 230B - Codeforces codeforces.com 조건 2초, n (1 ≤ n ≤ 10^5), xi (1 ≤ xi ≤ 10^12) 접근 이 문제는 약수가 3개인 수를 구한다. 약수가 3개인 수가 뭘까? 잘 생각해보면 소수를 ^2하면 약수가 3개인 수를 구할수 있음을 깨달을 수 있다. ex) 소수 2, 3, 5, 7의 제곱수들을 보면 4, 9, 25, 49로 모두 약수가 3개인 수들이다. 그렇다면 소수만 빨리 풀수 있다면 이 문제도 시간내에 충분히 풀수있을것이다. 풀이방법 일단 범위는 루트를 씌워 구할것이기 때문에 10^12의 루트를 씌운 10^6 + 1로 설정했다. 그외에는 그냥 에라스토테네스..

https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전기용품의 플러그를 뺐다 꽂았다 하는 불편함을 겪고 있다. 그래서 준규는 자신의 생활 패턴을 분석하여, 자기가 사용하고 있는 전기용품의 사용순서를 알아내었고, 이를 기반으로 플러그를 빼는 횟수를 최소화하는 방법을 고안하여 보다 쾌적한 생활환경을 만들려고 한다. 예를 들어 www.acmicpc.net 풀이방법 현재 연결되어 있는 가전제품중에 이후에 제일 늦게 사용되거나 더이상 사용되지 않는 가전제품을 빼고 연결하면 된다. 처음에 ..