8/26 Problem Solving

15927 회문은 회문아니야!! (G5)

 

문자열 s가 주어졌을때 길이를 n이라고 하자. s 자체가 팰린드롬이 아니라면 n을 출력해주면 된다. s가 팰린드롬이라면 만약에 전체가 똑같은 글자로 이루어진 팰린드롬이면 모든 부분문자열이 팰린드롬이므로 -1이 답이다. 그렇지 않다면 맨 앞이나 뒤에서 하나만 빼주면 팰린드롬이 아니게 된다. 즉 n-1이 답이다.

 

http://boj.kr/3cb717aee0e141adb4e5edd5b5b46afb

 

 

14370 전화번호 수수께끼 (Large) (G4)

 

각 숫자에 대응하는 영어 단어에서 고유한 문자를 찾는다.

 

0 : ZERO (Z)

2 : TWO (W)

4 : FOUR (U)

6 : SIX (X)

8 : EIGHT (G)

1 : ONE (O) - O는 0에서 쓰였으므로 0을 먼저 처리하고 1을 처리한다.

3 : THREE (T) - T는 8에서 쓰였으므로 8을 먼저 처리하고 3을 처리한다.

5 : FIVE (F) - F는 4에서 쓰였으므로 4를 먼저 처리하고 5를 처리한다.

7 : SEVEN (S) - S는 6에서 쓰였으므로 6을 먼저 처리하고 7을 처리한다.

9 : NINE (I) - I는 5,6에서 쓰였으므로 5,6을 먼저 처리하고 9를 처리한다.

 

숫자들이 존재하면 카운팅해서 담아준 후 정렬해서 출력해준다.

 

http://boj.kr/9bd1745f76a043b2b2139d5bb62dd304

 

 

15553 난로 (G5)

 

친구들이 Ti에 도착하고 Ti+1에 나간다. 친구들이 있을 때는 난로를 항상 켜야하고 혼자 있을 때는 최대한 난로를 안 키려고 한다. 그리고 최대 K번 난로를 켤 수 있다. 그러면 친구들이 있는 시간대에는 모두 포함을 하되 혼자 있는 구간을 최대한 줄여야 한다. 혼자 있는 구간의 길이를 구해서 정렬 한후 가장 큰 K-1개 구간을 제거해준다. 그리고 나머지 구간들을 이용해서 K개의 난로가 켜져있는 구간을 구할 수 있다. 그림을 그려보면 쉽게 이해할 수 있다.

 

http://boj.kr/30ea3916b62243a8947d160ea84d5e44

 

 

1322 X와 K (G4)

 

X + Y = X | Y 를 만족하는 K번째로 작은 자연수 Y를 찾아야 한다. 이 식이 성립하려면 Y가 X와 겹치지 않는 비트를 가져야 한다. 즉, Y의 비트 중에서 X에서 0인 비트에만 1을 사용할 수 있다. 비트마스크를 적절히 활용하여 Y를 찾을 수 있다. bit라는 변수를 두고 현재 탐색하고 있는 비트 위치를 나타낸다. 처음에는 1로 시작하여 left shift 하면서 탐색한다. 탐색하면서 X & bit가 0인 경우, 즉 X의 해당 비트가 0이라면 그 자리에 K의 현재 비트를 Y에 반영한다. K에서 현재 비트를 사용한 후에는 right shift 한 후다음 비트를 준비한다. 모든 K의 비트를 사용할 때까지 이 과정을 반복하면 된다.

 

http://boj.kr/081d54e01649420a90c695f1a3f89d74

 

 

3019 테트리스 (G5)

 

테트리스 블록을 떨어트릴때 나올 수 있는 모든 모양에 대해서 필드의 높이들과 합이 맞는지 체크해보면 된다. 케이스 분류를 잘해서 빠짐없이 브루트포스를 하면된다.

 

http://boj.kr/209cddc282ba40caa629b54f4a36c393