https://www.acmicpc.net/problem/17175 17175번: 피보나치는 지겨웡~ 혁진이는 알고리즘 문제를 만들라는 독촉을 받아 스트레스다. 하지만 피보나치 문제는 너무 많이 봐서 지겹기 그지없다. 그러나 문제를 만들 시간이 없는 혁진이는 피보나치 문제를 응용해서 www.acmicpc.net 1차원 DP 문제였다. 피보나치 함수(이하 fibo) 의 호출횟수를 수동으로 살펴보도록 하겠다. fibo[0] = 1 fibo[1] = 1 fibo[2] = 3 fibo[3] = 5 fibo[4] = 9 .... 규칙을 파악할 수 있는가? fibo[k] = (1+fibo[k-1]+fibo[k-2]) 이다. 1은 자기자신 역시 호출되었기에 더해줘야 하는 수고 fibo[k-1]과 fibo[k-2] 는..

https://www.acmicpc.net/problem/14582 14582번: 오늘도 졌다 첫 번째 줄에는 9개의 정수가 주어지는데, 오늘 경기에서 울림 제미니스가 1회 초, 2회 초, ..., 9회 초에 낸 득점이 주어진다. 두 번째 줄에도 9개의 정수가 주어지는데, 스타트링크 걸리버스가 1회 www.acmicpc.net 문제에서 요구하는대로 구현하면 되는 문제. 제미니스가 이기고 있던 적이 있는지를 체크하는 플래그 변수 flag1, flag1이 켜져있는(이긴적이 있는) 상황에서 스타트링크가 이기고 있다면 flag2를 켜줬다. flag2가 켜져있는지 꺼져있는지의 여부가 정답이 된다. 각 회 초가 끝난 바로 뒤 flag1을 갱신해줘야 함에 유의해야한다. #include using namespace s..

https://www.acmicpc.net/problem/9527 9527번: 1의 개수 세기 두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오. 즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라 www.acmicpc.net 고민을 오래 해봐야 하는 문제 수의 범위가 크다. 일단 수의 범위가 매우 큰 편이라서, 전처리를 통해서 시간을 아낄 생각을 해봐야 한다. 대부분의 변수에서 long long 형이 필요하니까, 그냥 모든 변수 자료형을 ll으로 통일하면 깔끔해진다. cnt[k] 를 비트 k개 범위(0~2^k-1) 의 수들에서 등장하는 2진수 1의 개수의 합 으로 정의한다. 숫자 K가 i개의 ..

https://www.acmicpc.net/problem/16927 16927번: 배열 돌리기 2 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] www.acmicpc.net 입력으로 들어오는 회전수 R이 터무니없어서 뇌정지가 왔었던 문제. R이 터무니 없다는 부분에서 MOD연산을 활용해야한다는걸 눈치챌수 있다면 문제를 깔끔하게 해결할 수 있다. 입력으로 들어오는 배열을 겉껍질 한줄을 배열로, 그 안쪽 한줄을 배열로, 배열을 한껍질씩 벗겨가면서 도넛 모양의 화살표 고리를 하나..

https://www.acmicpc.net/problem/2229 2229번: 조 짜기 알고스팟 캠프에 N(1 ≤ N ≤ 1,000)명의 학생들이 참여하였다. 학생들은 열심히 공부를 하고 있었는데, 어느 날 조별 수업을 진행하기로 하였다. 조별 수업의 목적은 잘 하는 학생들과 덜 잘 하는 www.acmicpc.net DP 사용해서 해결한 문제. dp[k] : k명까지 조를 짰을때 잘 짜여진 정도의 최댓값 으로 정의한다. 또한, 인덱스 s부터 e까지의 사람들로 조를 편성했을때 조가 잘 짜여진 정도를 O(N) 에 구해내는 함수를 하나 작성하고, (for문을 통해 만들면 된다) 이를 cal(s,e)라고 정의한다. dp[1]은 당연히 0이 될 것이고, $k$보다 작거나 같은 수 $a$에 대해서 dp[a-1] +..

https://www.acmicpc.net/problem/18429 18429번: 근손실 웨이트 트레이닝을 좋아하는 어떤 대학원생은, 현재 3대 운동 중량 500의 괴력을 소유하고 있다. 다만, 하루가 지날 때마다 중량이 K만큼 감소한다. 예를 들어 K=4일 때, 3일이 지나면 중량이 488로 www.acmicpc.net 중량이 500 미만으로 떨어지는 일이 없도록하는 경우의 수를 구하는 문제. 입력으로 들어온 배열의 크기 N이 그렇게 크지 않아서 브루트포스를 통해 모든 경우를 다 생각해봐도 그리 오래 걸리지 않는다. 구현에는 c++의 next_permutation을 사용했다. 정렬된 배열에서 next_permutation을 사용하면 해당 배열을 통해 만들수 있는 모든 경우의 수를 한번씩 순회해 볼 수 ..

https://www.acmicpc.net/problem/15624 15624번: 피보나치 수 7 첫째 줄에 n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다. www.acmicpc.net 기초적인 1차원 DP에 대해 묻고있는 문제. $F_n = F_{n-1} + F_{n-2}$ 공식에 맞게 dp 테이블을 구현해주면 된다. 1e9+7로 나눈 나머지를 출력해줘야 하는데, 전부 저장해뒀다가 출력시에만 1e9+7로 나누려고 하는 경우 피보나치값들이 매우 커져서 오버플로우가 발생할 수 있다. 정수론 모듈러 연산의 특징에 의해 $(A \pm B) mod C = (A mod C \pm B mod C) mod C$ 이고, $A$, $B$ 가 각각 dp테이블의 값, $C$가 1e9+7(1,000..

https://www.acmicpc.net/problem/8911 8911번: 거북이 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 컨트롤 프로그램이 주어진다. 프로그램은 항상 문제의 설명에 나와있는 네가지 명령으로만 이루어져 www.acmicpc.net 이동경로가 주어질때, 이동경로들을 모두 포함하는 가장 작은 직사각형의 넓이를 구하는 문제. 이 문제를 깔끔하게 풀기 위한 핵심으로써, L과 R의 회전방향을 일관적으로 유지만 해준다면 거북이가 처음 쳐다보고 있는 방향은 아무런 관련이 없다는 것이다. 거북이가 만일 남쪽을 바라보고 있다고 하더라도, 그림에서 나온 평면을 180도 뒤집어서 시뮬레이션 가능하고, 이 경우에도 넓이는 같기 때문이다. 그런 관계로 내가..

https://www.acmicpc.net/problem/14620 14620번: 꽃길 2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다. 진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므 www.acmicpc.net 풀긴풀었다만 매우불쾌한문제;; N의 범위가 그리 크지 않아서 점 세개를 정하는 경우의 수를 브루트포싱해도 된다. 문제는 점 세개의 좌표를 정해주기 위해서 무려 "6중 포문" 이 필요하다는건데 ㅠㅠ x,y 좌표를 x*N+y로 뭉쳐서 3중포문으로 압축할 수 있다지만 일단 길고 장황하게 구현해봤다. 꽃들이 겹쳤는지 확인하기 위해서 tmp라는 배열에 꽃들을 직접 그려보고, 꽃으로 표시된 부분(1이다) ..

https://www.acmicpc.net/problem/14430 14430번: 자원 캐기 인류의 차세대 인공지능 자원 캐기 로봇인 WOOK은 인간 대신 자원을 캐는 로봇이다. WOOK은 언제나 제한된 범위 내에서 자원을 탐색하며, 왼쪽 위 (1, 1)부터 오른쪽 아래 (N, M)까지 자원을 탐색한다. www.acmicpc.net DP로 해결했던 문제 DP[i][j] 를 $(i,j)$ 까지 이동해서 채취할 수 있는 최대 자원 으로 정의한다. $(i,j)$ 로 이동하는 경우는 $(i-1,j)$ 에서 이동한 경우 $(i,j-1)$ 에서 이동한 경우 두가지 경우가 있으므로, DP[i][j] = MAX( DP[i-1][j], DP[i][j-1] ) + arr[i][j] 로 계산해주면 정답을 얻을 수 있다. D..