문제풀이-분할정복

1. 색종이 만들기

알고리즘 문제를 풀때 nxn의 격자판을 가지는 그림이 있다라면

알고리즘 좌표계에서는 1,1에서 오른쪽으로 가면 y값 증가

1,1에서 아래쪽으로 가면 x값 증가로 좌표계가 표현되어 마지막에 n,n

 

 

2. 종이의 개수

9개로 나누므로, 한 종이의 길이는 len/3

return문이 있어야 계속반복하는것을 막음

 

 

3. 쿼드트리

한가지의 숫자로 이루어져있지 않고 4등분 할때 괄호가 열림

4등분으로 나눈거를 다 보고나면 괄호 닫힘

%1d 는 한자릿수의 입력을 받아 구분

 

 

추가적으로

만약 23:59 형식으로 받아야 하는게 정해져있다면 scanf가 알아서 : 기준으로 구분됨

scanf("%d:%d") 

 

4. Z문제

1초에 for문 1억번 걸리는

연산이 1억번 걸린다 : 1초

 

근데 이 문제의 조건은 n은 15까지이므로, 2^15 * 2^15 = 10억번 : 10초

라서 단순 분할정복으로 하면 시간이 초과된다.

확인하려고하는 r,c가 확인하려고 하는 범위안에 r,c가 포함되어있다면 

네등분하고,

포함되어있지 않다면, 칸 수를 확인 cnt += len* len 으로

 

5. 별찍기 -10

 

6. 곱셈

지수가 홀수인지 아닌지 확인,

홀수라면 나누기 2한값에 밑을 한번더곱하고

짝수라면~

 

---

팀대회 문제풀이

 

1. 칸토어 집합

 

기저조건을 작대기 하나일때

중앙이면 빈칸

왼족오른쪽은 짝대기 긋는것으로 생각하자

 

flag는 그릴수 있느냐 없느냐, 판별에 대한 인자

가운데 중간은 아예 공백이어야해서 false값

 

2. 투에모스문자열

반전된 문자열

뭔소린지 이해안감

 

 

3. 특별상

기저조건 : 분할을 해 나가면서 한변의 길이가 2가될ㄸ

두번째로 큰값을 찾아서 return

 

 

4. 222풀링

 

]

 

5. 종이접기

왼쪽만 봐도 되는이유

왼족과 오른족은 완벽학 ㅔ대칭

 

6. 별찍기

최소가 3일때 (기저조건)