종신1재정2시경3

https://www.acmicpc.net/problem/15673

수열에서 연속 부분 수열 두개를 골라 그 곱이 가장 클 때 얼마나 클지 알아내야 한다.

연속 부분 수열이 얼마나 클지를 알아내는 방법은 디피 문제를 풀 때 쉽게 접할 수 있는 문제다.

dp[x]를 x번째 인자를 포함한 부분 수열 중 합이 가장 큰 수를 저장하게 정의해 놓으면,

dp[x]는 dp[x-1]이 음수인 경우와 양수인 경우로 나눠 원타임에 값이 정해진다.

또한 새로운 디피 배열 lmax를 정의할 수 있게 되는데,

이번엔 lmax[x]는 x번째 인자를 반드시 포함하지 않아도, x까지 수열의 부분 수열 중 합이 가장 큰 수를 저장한다고 정의해 놓으면,

lmax[x] = max(lmax[x-1], dp[x])로 원타임에 값이 정해진다.

즉 x가 포함되던지 안되던지 두 케이스 중 큰 값으로 정해지는 것이다.

이를 응용해서 왼쪽에서 부터, 오른쪽에서 부터, 최대합 부분수열, 최소합 부분수열을 모두 n타임에 구할 수 있다.

그러고 난 다음 부분 수열 두 개로 나눌 기준점을 n개 중에 골라서 비교하는 작업도 n타임에 수행할 수 있다.

https://www.acmicpc.net/problem/15668

0 ~ 9 까지 숫자 카드 스티커들을 한 번씩만 사용해 n = a + b 의 a와 b를 만들어야 한다.

여러 풀이 중에 내 생각에 제일 기똥찬 풀이는,

a와 b중에 작은 수를 b라고 하면, b의 가능 범위가 작아지므로, 완탐으로 때릴 수 있다는 것이다.

b에 스티커 5장을 쓰면 a도 5장이 되므로 b엔 최대 5장까지만 쓸 수 있다.

또한 b의 맨 앞자리는 끽 해야 8이므로, 1~87654가 b의 가능범위이다.

b가 정해지면 a도 정해지므로, 구만번 만에 풀리는 문제.

https://www.acmicpc.net/problem/16116

구현이지만 논리력에 따라 // 관찰력에 따라 코드가 짧아질 수 있는 문제

다음을 관찰하면 코드가 짧아진다.

한 큐브가 [a b c] 였다면, 반드시 나머지 일곱 개 중에 윗 그림과 같은 세 개의 큐브가 존재해야 한다.

헌데 큐브는 요리 조리 돌려도 똑같기 때문에

한 큐브 마다 -> 세 가지 방향으로 -> 나머지 7가지 큐브 중에 -> 두면이 맞닿고 같은 큐브가 존재(중요) -> 그것도 1개만

같은 조건을 전부 만족한다면 조립할 수 있다.