컴공생 일상 블로그 컴공생 일상 블로그

https://www.acmicpc.net/problem/2292 2292번: 벌집 위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌�� www.acmicpc.net 최소거리는 감싸진 횟수와 동일하다. 1 6 12 18 24 ... #include int main() { int N; int sum=1; int n=1; scanf("%d", &N); while(sum < N){ sum += 6*n++; } printf("%d\n", n); return 0; }

https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그�� www.acmicpc.net 최대한 적은 봉지를 들고간다 -> 최대한 5kg봉지를 많이 들고간다. 따라서 5로 나누어 떨어지면, 몫이 답이된다. 만약 5로 바로 나누어 떨어지지 않으면 3kg봉지를 하나씩 늘려가면서 봉지를 세면 된다. 안나눠 떨어질경우 -1출력 #include int main() { int N, result=0; scanf("%d", &N); //3~5000 while(N%5!=0){ N-=3; result++; }..

www.acmicpc.net/problem/1712 1712번: 손익분기점 월드전자는 노트북을 제조하고 판매하는 회사이다. 노트북 판매 대수에 상관없이 매년 임대료, 재산세, 보험료, 급여 등 A만원의 고정 비용이 들며, 한 대의 노트북을 생산하는 데에는 재료비와 www.acmicpc.net 매년 나가는 고정 비용 : A만원 한대의 노트북을 생산하기 위한 가변 비용 : B만원 노트북을 한대 생산하기 위한 비용 A+B 노트북을 N대 생산하기 위한 비용 A+B*N 노트북 가격C만원 일때, 생산 수를 늘려가다보면 총수입이 총비용보다 많아지는 시점이 손익분기점(Break-even point)가 됨 C*N >= A+B*N 이 true가 되는 시점의 N을 구하면됨 A+B*N - C*N =< 0 A+N*(B-C) =..

https://www.acmicpc.net/problem/1065 1065번: 한수 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 �� www.acmicpc.net 한수? 한수는 각 자리수가 등차수열을 이루는 수를 칭한다. 또한 한자리수와 두자리수의 경우 모두 한수에 포함된다. ex) 135 +2의 공차를 가짐, 840 -4의 공차를 가짐 문제에서 N의 범위를 1~1000으로 줬기 떄문에 아래와 같이 풀이 할 수 있다. #include int check_hansu(int num){ int a=num/100; int b=(num%100)/10; int c=n..

https://www.acmicpc.net/problem/1110 1110번: 더하기 사이클 0보다 크거나 같고, 99보다 작거나 같은 정수가 주어질 때 다음과 같은 연산을 할 수 있다. 먼저 주어진 수가 10보다 작다면 앞에 0을 붙여 두 자리 수로 만들고, 각 자리의 숫자를 더한다. 그 다음, www.acmicpc.net #include int return_n(int p, int q){ return q*10 + (p+q)%10; } int main() { int N,n; //N 0~99 int a,b; //ab int clen=0; scanf("%d", &N); n=N; do{ a=n/10; b=n%10; n=return_n(a,b); clen++; }while(N!=n); printf("%d\n",..

https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 손으로 끄적거리다보면 피보나치수열과 비슷함을 알 수 있다. 1 1 2 3 5 7 ... #include int main(){ int i,n; int result=1, a=1, b=1; scanf("%d",&n); for(i=2;i

1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 동적계획법을 사용한 문제 Top_down 재귀문을 사용해 풀이하면... n에 대해 min(3또는 2로 나눈 경우, n-1의 경우)에서 작은 값만을 선택해가면서 답을 구할 수 있다. ex) 10 10은 2로 나누어지기 떄문에 min(make_1(5), make_1(9)) 5는 1+make_1(4) 9는 1+min(make_1(3), make_1(8)) ... 10 -> 9 -> 3 -> 1 결과값 : 4 #include int min(int a, int b){ return a > b ? b : a; //최소값 return } int make_1(int n){ if(n==1) r..

동적 계획법 - 큰 문제를 작은 문제로 나누어 푸는 알고리즘이다. 작은 문제들을 해결한 뒤, 해당 답을 저장해놓고 그보다 큰 문제를 풀이하는데 앞서 저장해둔 값들을 활용해 풀어나간다. DP(Dynamic Programming)을 사용 조건 1. 작은 문제로 쪼갤 수 있다. 2. 작은 문제에서 구한 값은 큰 문제를 풀이할 때도 동일한 값이여야 한다. 이때, 메모이제이션(Memoization)이 활용된다. +Memoization : 계산한 값을 메모리에 저장해두고, 여러번 같은 값 계산을 피하는 최적화 기법(실행속도를 높이고, 메모리를 절약할 수 있다.) EX) Fibonacci수열 피보나치 수열은 1, 1, 2, 3, 5, 8, 13, 21 ... 의 수열이다. 즉, fibo(3) = fibo(2) + f..