Purple Haskell(2)

https://codeforces.com/group/DEuKcKDfls/contest/227547

오늘 연습

A.Flipping Game

길이 n(<=100)인 0,1로만 구성된 배열이 주어지고, 여기서 연속한 구간을 하나 아무거나 골라 뒤집을 수 있다고 했을 때 1의 개수를 최대화하는 문제다.

n 제한이 굉장히 작으므로 그냥 모든 가능한 배열 만들어서 그 중 제일 큰 걸 구했다. 이런 거 할 땐 list comprehension이 제일 편한 듯

B. Candy Bags

1 ~ n^2(n은 짝수, n <= 100)까지의 수를 합이 동일한 n개의 배열로 나누는 문제다. 맨앞 맨 뒤에서 각각 n/2개씩 가져오는 걸 반복하면 되는데, 구현을 어떻게 하면 좋나 좀 고민이 됐다. 내가 생각한 과정은 다음과 같다.

1. 일단 1 ~ n^2으로 구성된 배열을 만든다

2. n/2 사이즈로 전부 분할한다

3. 맨 앞, 맨 뒤에서 한 덩이씩 가져와서 n개짜리 배열을 만든다

아주 마음에 들진 않지만 무난한 듯. n/2 사이즈로 분할하는게 조금 짜증났다

C.  Levko and Table

n*n( n <= 100) 사이즈 행렬을 만드는데, 행렬의 각 행과 열이 전부 합이 k가 되게 만드는 문제다. 말이 그렇지 주대각선에 k 박으면 무조건 행, 열 각각 전부 합이 k가 되므로 나머진 전부 0으로 채워져있고 주대각선에 k 들어간 행렬을 만들면 된다.

나는 [k,0,0,0,...] 으로 만들어진 배열을 만들고 이걸 iterate 함수를 이용해 앞에 0을 덧붙이며 n개씩 자르는 식으로 구현했다. 이런거 짤 땐 iterate가 정말 강력한 것 같다

D. Levko and Permutation

1~n까지 숫자로 이루어진 길이 n 순열에 대해, i번째 숫자가 Pi라고 하자. gcd(i, Pi) > 1인 위치가 k개가 되는 순열을 아무거나 하나 찍는게 문제다.

방법은 되게 다양하게 있을텐데, 나는 gcd(x, x+1) = 1, gcd(a, a) = a 인 걸 이용해서 풀었다. k = n인 경우는 불가능하니 -1, k = n -1인 경우는 [1..n] 그대로 출력, 그 외의 경우는 2 ~ k+1 번 위치에 숫자 그대로 둬서 gcd(i, Pi) > 1인거 k개를 확보한 후 나머지 위치는 전부 gcd가 1이 되게 배치하는 식으로 구했다.

경우만 정리하고 나면 구현하긴 간단한 듯. 예전에 C++로 짰을 땐 좀 다른 방식으로 풀었었는데 그 방식은 haskell로 짜긴 안 적합했다. 함수형 언어로 구현하기 쉬운 형태의 답안을 잘 고민하는 연습도 필요할 것 같다

 

암튼 다 푸는데 대충 40분쯤 걸린 것 같은데, 중간중간 딴짓한 거 감안해도 좀 너무 오래 걸림. 1년전에 C++로 풀었을 때 다 푸는데 30분쯤 걸렸으니, 이거 C++로 푼 기록들 보고 대충 비슷한 시간 안에 문제들 해결하는 걸 목표로 연습을 해야겠다. 아직은 haskell로 깔끔하게 짤 수 있는 방법도 바로 안 떠오르고, 방법을 생각해도 그걸 빠르고 정확하게 코드로 옮기는 게 잘 안 되는 것 같다.