https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 배열을 어떻게 만들어야 할지 고민했던 문제. dp배열을 만든 뒤로는 그냥 무난하게 풀어냈다. #include int dp[1001][3] = {0}; int min(int a, int b){ return a>b?b:a; } int index(int k){ if(k==3){return 0;} if(k==-1){return 2;} return k; } int main(){ int..
https://www.acmicpc.net/problem/1016 1016번: 제곱 ㄴㄴ 수 첫째 줄에 min과 max가 주어진다. min은 1보다 크거나 같고, 1,000,000,000,000보다 작거나 같은 자연수이고, max는 min보다 크거나 같고, min+1,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 시간초과가 나서 되게 고민했던 문제. #include #include #define ll long long int bool chk[1000001] = {0}; int main(){ ll min,max; ll sum = 0; scanf("%lld %lld", &min, &max); sum = max - min + 1; for(ll i=2; i*i
if문 처리가 굉장히 어마어마하게 귀찮았던문제 마치 ' 두 박스 ' 를 연상시킨다 좀 더 고민하면 잘 줄여낼수있을거같긴한데... https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net #include #include int arr[10001] = {0}; int main(){ int n,ans=0; scanf("%d", &n); for(int i=0; i=1; i--){ if((arr[i-1]>0 && arr[i-1]!=1) || (arr[i]
2차원 DP 를 통해 풀어줄 수 있다. www.acmicpc.net/problem/4811 4811번: 알약 입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다. www.acmicpc.net dp[a][b]는 완벽한 상태의 알약이 a개, 반개짜리 알약이 b개일때의 문자열의 개수이다. 완벽한 알약을 하나 복용하고 반개짜리 알약으로 만들어 줄 수 있으므로, dp[a-1][b+1]의 경우가 생길 수 있고, 반개짜리 알약이 있는 경우 ( b > 0 ) 에는 반개짜리를 먹는 경우도 추가로 더해준다. 굳이 a==0 && b==0일때 탈출하지 않는 이유는 어차피 dp[a][k]에서 a가 ..
www.acmicpc.net/problem/20309 20309번: 트리플 소트 $N$은 $3, 4, 5$ 중 하나이다. www.acmicpc.net 생각의 전환 이 문제를 풀기위해서 반드시 사고해야할 점은 "세개를 동시에 뒤집는 것" 이 무엇을 의미하는지 알아야한다 세개를 동시에 뒤집게 되면 세개 중 가운데에 있는 수는 항상 제자리에 있게 되고, 결과적으로 보자면 i 번째 수를 i+2번과 바꾸는것과 같게 되어서 홀수자리는 홀수자리끼리만 / 짝수자리는 짝수자리끼리만 바꿀수 있게 됩니다. 따라서 홀수자리에 짝수가 나온다면 절대 바꿀수 없으므로 NO, 아니면 YES를 출력하게 짜주면 됩니다. #include int arr[345678] = {0}; int main(){ int n; bool ans = tru..
https://www.acmicpc.net/problem/8464 8464번: Non-Squarefree Numbers Your program should output one integer, the n-th non-squarefree number. www.acmicpc.net 1577번의 정확히 정 반대에 해당하는 문제. 조금만 수정해줘도 쉽게 AC를 받을 수 있다. --- 소스코드 내립니다 --- setup이나 f함수의 역할은 같고, 기존의 f 함수는 k 이하의 squarefree number의 수를 세기 때문에, mid - f(mid)를 통해서 mid 이하의 non-squarefree number의 수를 세줄 수 있다. 그리고 탐색범위가 k의 영향에서 벗어나는지 WA가 나와서 그냥 e에 엄청 큰 수 ..