8주차 복습 문제 해설

www.acmicpc.net/group/practice/9883/20

어려운 문제는 D번, E번 문제라고 생각합니다. D번은 다른 분이 삼성 기출 문제 대비로 만든 문제로 3월 27일 모의테스트에서 진행했었던 문제이고, E번은 옛날 삼성 역량테스트 기출 문제입니다.

 

 

1. BOJ 9971 The Hardest Problem Ever

www.acmicpc.net/problem/9971

9971번: The Hardest Problem Ever

 

카이사르 암호 문제입니다.

 

일단 입력값을 받는 코드를 짭시다. START 부분은 ENDOFINPUT이라는 입력값이 나오면 종료해야하므로 변수를 하나 할당해서 break문을 사용합니다. 그리고 END 부분은 아예 쓸모가 없으므로 변수 할당 없이 input()함수만 사용합니다.

while 1:
    a = input()
    if a == 'ENDOFINPUT': break
    s = list(input())
    input()

 

나머지 부분은 깃북에서 배운대로 아래와 같은 과정을 거치면 됩니다.

F가 A로 바뀌므로 21칸을 건너뛰어야 만들 수 있다는 것을 알 수 있습니다.

 

 

 

while 1:
    a = input()
    if a == 'ENDOFINPUT': break
    s = list(input())
    input()

    for i in range(len(s)):
        if 65 <= ord(s[i]) <= 90:
            x = ((ord(s[i])-65)+21)%26
            s[i] = chr(x+65)
    print(''.join(s))

 

 

 

 

2. BOJ 3035 스캐너

www.acmicpc.net/problem/3035

3035번: 스캐너

 

문제 출력에 힌트가 나와있습니다. 새로운 배열의 크기는 R * ZR 이고, C * ZC 입니다.

 

그래서 r, c 와 배열 arr을 입력 받고, 새로운 배열의 크기인 nr, nc와 새로운 배열 narr을 만들어줍니다. 이때 nr은 r * zr이고, nc는 c * zc 입니다.

 

r,c,zr,zc = map(int,input().split())
arr = list(list(input()) for _ in range(r))
nr, nc = r*zr, c*zc
narr = list(list(' ')*nc for _ in range(nr))

 

이제 narr에 값을 넣어야하는데, 일단 arr에 접근하려면 2중 for문을 이용하여 arr[i][j]로 접근할 수 밖에 없습니다. 그리고 이 값을 복사해서 narr에 넣어야하는데, 복사하려면 zr, zc만큼 2중 for문으로 돌려야하는 것을 알 수 있습니다.

 

r,c,zr,zc = map(int,input().split())
arr = list(list(input()) for _ in range(r))
nr, nc = r*zr, c*zc
narr = list(list(' ')*nc for _ in range(nr))

for i in range(r):
    for j in range(c):
        for x in range(zr):
            for y in range(zc):
                blah blah

 

이제 narr 값에 접근을 해야하는데, 값을 nx와 ny라고 합시다.

 

3 3 2 2
.x.
x.x
.x.

 

이것을 입력값 예시로 들면 아래와 같은 출력물이 나오게 됩니다.

 

..xx..
..xx..
xx..xx
xx..xx
..xx..
..xx..

 

여기서 세로로 첫 번째 줄(1열)만 그림으로 그려보면

이렇게 표현할 수 있는 것을 알 수 있습니다.

가로로 첫 번째 줄(1행)만 그림을 그려보면 윗 그림과 똑같습니다.

 

이렇게 빨간 박스처럼 2x2로 구역을 i 와 j에 각각 zr과 zc를 곱해주는 것이고, 2x2 칸을 전부 같은 값으로 해야하기 때문에 x와 y를 더해주는 것입니다.

그래서 수식으로 말하면 행은 zr * i + x이고, 열은 zc * j + y입니다.

 

그리고 이제 출력을 해주면 됩니다

r,c,zr,zc = map(int,input().split())
arr = list(list(input()) for _ in range(r))
nr, nc = r*zr, c*zc
narr = list(list(' ')*nc for _ in range(nr))

for i in range(r):
    for j in range(c):
        for x in range(zr):
            for y in range(zc):
                nx, ny = i*zr+x, j*zc+y
                narr[nx][ny] = arr[i][j]
for i in range(nr):
    print(''.join(narr[i]))

 

다른 예제도 확인해보면 위와 같다는 것을 알 수 있습니다.

 

 

 

 

3. BOJ 13986 Gravity

www.acmicpc.net/problem/13986

13986번: Gravity

이번에 삼성 역량 테스트 문제중에 하나가 이 중력을 이용하여 물체를 바닥으로 떨어뜨리는 문제가 있었습니다.

 

풀이 방법은 2가지로 하나는 3중 for문과 하나는 2중 for문과 큐로 만들 수 있습니다.

 

3-1. 3중 for문

일단 arr[x][y] = 'o'이면 arr[x+1][y] = '.'여야 o를 아래 칸으로 내릴 수 있습니다.

 

o..
...
...

이런 예시가 있으면 2번을 아래로 내려야하고

 

o..
...
...
...
...

이런 예시가 주어지면 4번을 아래로 내려야 합니다.

 

이것을 통해 n-1번만 반복해도 모든 o를 아래로 내릴 수 있다는 것을 알 수 있습니다.

 

그래서 arr[x][y]와 arr[x+1][y]를 확인해야하므로 나머지 2중 for문은 for x in range(n-1)과 열을 나타내는 for y in range(m)을 적어주면 됩니다.

 

n,m = map(int,input().split())
arr = list(list(input()) for _ in range(n))
for i in range(n-1):
    for x in range(n-1):
        for y in range(m):
            if arr[x][y] == 'o' and arr[x+1][y] == '.':
                arr[x][y], arr[x+1][y] = '.', 'o'
for i in range(n):
    print(''.join(arr[i]))

여기서 4줄과 5줄의 순서를 바꾸어도 상관이 없습니다.

 

 

저 같은 경우에는 i부분에서 n-1이나 n이나 실행 속도가 비슷하기 때문에 for i in range(n)으로 바꿔서 사용하는 편입니다.

 

n,m = map(int,input().split())
arr = list(list(input()) for _ in range(n))
for i in range(n):
    for x in range(n-1):
        for y in range(m):
            if arr[x][y] == 'o' and arr[x+1][y] == '.':
                arr[x][y], arr[x+1][y] = '.', 'o'
for i in range(n):
    print(''.join(arr[i]))

 

 

 

3-2. 2중 for문 + 큐

2중 for문은 위에 나온 코드인 x, y와 비슷합니다. 하지만 이번엔 바닥부터 확인해가면서 큐에 빈공간을 넣어주는 방식이기 떄문에 살짝 다릅니다.

 

1. '.'이 나올 때: 큐에 해당 좌표를 추가해줍니다.

2. '#'이 나올 때: #이 나온 곳이 바닥이므로 q = deque()로 큐에 있는 값들을 모두 없애줍니다.

3. 'o'가 나올 때: o가 나오면 큐에 값이 들어가있는지 확인합니다. 큐에 값이 있으면 바닥에 떨어질 값이 있으므로 o가 있는 좌표를 빈공간(.)으로 만들어주고, 큐에 있는 값을 빼내 해당 좌표를 o로 만들어줍니다. 그리고 원래 o가 있던 좌표를 큐에 넣어주면 됩니다.

 

 

이렇게 해서 만들어진 코드가 아래와 같습니다.

from collections import deque
n, m = map(int,input().split())
arr = list(list(input()) for _ in range(n))
for j in range(m):
    q = deque()
    for i in range(n-1,-1,-1):
        if arr[i][j] == '.': q.append(i)
        if arr[i][j] == '#': q = deque()
        if arr[i][j] == 'o' and len(q):
            arr[i][j] = '.'
            arr[q.popleft()][j] = 'o'
            q.append(i)
for i in range(n):
    print(''.join(arr[i]))

이 코드는 큐에다가 행값만 넣었는데, 우리는 물체가 떨어질 때 arr[x][y]에서 x행이 어느 행까지 떨어지는지 확인하기 때문에 굳이 열을 넣을 필요는 없어서 그렇게 했습니다.

 

 

 

두 작동 방식중에 맘에 드는 방법을 하나 선택해서 외우고 사용하면 됩니다. 저 같은 경우엔 짧은 코드를 좋아해서 3.1 방식을 외워서 사용하는 편입니다.

 

 

 

 

4. BOJ 21275 폰 호석만

www.acmicpc.net/problem/21275

21275번: 폰 호석만

 

 

3월 27일 모의테스트(www.acmicpc.net/problem/21275)에서도 나왔던 문제입니다.

 

youtu.be/Zt38XizwbAw?t=413

 

풀이는 이 영상을 보셔도 상관 없습니다.

 

 

이 문제는 for문을 이용하여 2진법부터 36진법까지 확인해 진법 변환을 이용하여 같은 10진수가 나오는 값이 있는지 확인하면 되는 문제입니다.

 

일단 '0'부터 '9', a부터 z까지를 숫자값으로 저장해야합니다. 그래서 딕셔너리에 '0' ~ 'z'의 값을 key값으로 설정하고, value값은 0 ~ 35로 설정해줍니다.

 

a, b = input().split()
val = {str(i): i for i in range(10)}
val.update({chr(97+i):i+10 for i in range(26)})

 

이제 a와 b를 10진법으로 바꾸면 되는데요. 이것은 int()함수를 이용하여 10진수로 바꿀 수 있습니다. 우리는 2진법부터 36진법까지 확인해야 하는데, 만약 a의 값이 bbbb인데 2진법을 확인하면 에러가 나올 것입니다. 2진법에서는 1과 0만 있는데 bbbb가 2진법일 수 없기 때문입니다.

 

그래서 val 딕셔너리를 이용해 a와 b가 가지고 있는 val의 최대값을 찾아주면 됩니다. 그리고 val에 값을 넣어보면 val[1] = 1, val[a] = 10이 나오는데 a와 b가 1까지 나온다면 2진법, a까지 나온다면 11진법이기 때문에 시작점을 (최대값 + 1)로 설정해주면 됩니다.

 

a, b = input().split()
val = {str(i): i for i in range(10)}
val.update({chr(97+i):i+10 for i in range(26)})

max_a = 2 # 2진법부터 시작하므로
for i in range(len(a)):
    max_a = max(max_a, val[a[i]] + 1)
max_b = 2
for i in range(len(b)):
    max_b = max(max_b, val[b[i]] + 1)

 

그리고 이제 각 진법들을 10진법으로 전환해주면 됩니다. 우리는 답을 출력할 때 어느 진법에서 10진법으로 변환했는지 출력해야하므로 리스트를 하나 만들어서 [원래 진법, 10진법으로 변환한 값]으로 넣어주면 됩니다.

 

a, b = input().split()
val = {str(i): i for i in range(10)}
val.update({chr(97+i):i+10 for i in range(26)})

max_a = 2
for i in range(len(a)):
    max_a = max(max_a, val[a[i]] + 1)
max_b = 2
for i in range(len(b)):
    max_b = max(max_b, val[b[i]] + 1)

list_a = []
for i in range(max_a, 37):
    list_a.append([i, int(a, i)])
list_b = []
for i in range(max_b, 37):
    list_b.append([i, int(b, i)])

 

이제 마지막으로 list_a와 list_b에 같은 값이 있는지, 그리고 문제에서 a진법과 b진법이 같으면 안된다고 했으므로 이 두가지 조건을 확인하면 됩니다. 조건들을 통과하면 ans라는 리스트에 저장합니다.

ans에 저장할 리스트는 [10진수 값, a 진법, b 진법] 입니다.

 

a, b = input().split()
val = {str(i): i for i in range(10)}
val.update({chr(97+i):i+10 for i in range(26)})

max_a = 2
for i in range(len(a)):
    max_a = max(max_a, val[a[i]] + 1)
max_b = 2
for i in range(len(b)):
    max_b = max(max_b, val[b[i]] + 1)

list_a = []
for i in range(max_a, 37):
    list_a.append([i, int(a, i)])
list_b = []
for i in range(max_b, 37):
    list_b.append([i, int(b, i)])

ans = []
for i in range(len(list_a)):
    for j in range(len(list_b)):
        if list_a[i][1] == list_b[j][1] and list_a[i][0] != list_b[j][0]:
            ans.append([list_a[i][1], list_a[i][0], list_b[j][0]])

 

이제 답을 출력해야하므로 ans의 길이가 0이면 Impossible, 1이면 ans를 출력, 2 이상이면 Multiple을 출력하면 됩니다.

 

a, b = input().split()
val = {str(i): i for i in range(10)}
val.update({chr(97+i):i+10 for i in range(26)})

max_a = 2
for i in range(len(a)):
    max_a = max(max_a, val[a[i]] + 1)
max_b = 2
for i in range(len(b)):
    max_b = max(max_b, val[b[i]] + 1)

list_a = []
for i in range(max_a, 37):
    list_a.append([i, int(a, i)])
list_b = []
for i in range(max_b, 37):
    list_b.append([i, int(b, i)])

ans = []
for i in range(len(list_a)):
    for j in range(len(list_b)):
        if list_a[i][1] == list_b[j][1] and list_a[i][0] != list_b[j][0]:
            ans.append([list_a[i][1], list_a[i][0], list_b[j][0]])

if len(ans) == 0: print('Impossible')
elif len(ans) == 1: print(' '.join(map(str,ans[0])))
else: print('Multiple')

 

 

 

 

 

5. BOJ 14889 스타트와 링크

www.acmicpc.net/problem/14889

14889번: 스타트와 링크

거의 4년 전에 나온 삼성 역량테스트 문제였던 스타트와 링크입니다.

최근에 나온 문제랑 이 문제를 비교해보면 난이도가 엄청나게 올라갔다는 것을 깨닫게 됩니다.

이 차이를 보면 제가 취업할 때에는 얼마나 어려워질지 가늠이 안가네요..

 

 

이 문제는 순열과 조합을 이용하여 풀 수도 있고, 아니면 8주차에서부터 배웠던 재귀 함수로 구현해서 풀 수 있습니다.

 

순열과 조합으로 풀 수 있는 이유는 N명을 두 팀으로 나누기 때문에 N//2명을 뽑아서 한 팀으로 정하면 자동적으로 나머지 N//2명은 다른팀이 됩니다. 그래서 조합을 이용하여 문제를 풀 수 있습니다. 순열로 풀면 좀 더 오래 걸리겠죠

 

출력값은 차이의 최소값을 출력해야 하니까 ans = float('inf')로 무한대의 값을 설정해주면 됩니다.

from itertools import combinations as cb

n = int(input())
s = list(list(map(int,input().split())) for _ in range(n))
arr = [i for i in range(n)]

ans = float('inf')

 

문제에서는 1번 사람부터 N번 사람으로 나와있지만 우리는 s[i][j]로 접근해서 점수를 챙겨야하기 때문에 0번 사람부터 N-1번 사람으로 설정했습니다.

 

그리고 이제 cb(arr, n//2)를 이용하여 팀원을 반절로 나누면 됩니다.

 

from itertools import combinations as cb

n = int(input())
s = list(list(map(int,input().split())) for _ in range(n))
arr = [i for i in range(n)]

ans = float('inf')
for t1 in cb(arr, n//2):
    blah blah

 

나머지 팀은 set() 을 이용하여 arr과 t1에 차집합을 이용해서 나머지 팀의 멤버를 구합니다. 그리고 리스트로 변환해주면 됩니다.

 

from itertools import combinations as cb

n = int(input())
s = list(list(map(int,input().split())) for _ in range(n))
arr = [i for i in range(n)]

ans = float('inf')
for t in cb(arr, n//2):
    t1 = t
    t2 = list(set(arr) - set(t1))

 

이제 t1의 점수와 t2의 점수를 구해주면 됩니다. 이것은 단순 2중 for문으로도 할 수 있고, 아니면 조합을 이용하여 n//2명의 팀원중 2명을 선택해 점수를 더해주는 방법도 있습니다.

 

from itertools import combinations as cb

n = int(input())
s = list(list(map(int,input().split())) for _ in range(n))
arr = [i for i in range(n)]

ans = float('inf')
for t in cb(arr, n//2):
    t1 = t
    t2 = list(set(arr) - set(t1))

    s1 = 0
    for x, y in cb(t1, 2):
        s1 += arr[x][y]
    s2 = 0
    for x, y in cb(t2, 2):
        s2 += arr[x][y]

 

우리는 s1과 s2의 차이가 최소가 되는 점수를 출력하는 것이므로 절대값을 이용하여 s1과 s2의 점수차를 구해서 ans의 값을 업데이트하면 됩니다.

 

from itertools import combinations as cb

n = int(input())
s = list(list(map(int,input().split())) for _ in range(n))
arr = [i for i in range(n)]

ans = float('inf')
for t in cb(arr, n//2):
    t1 = t
    t2 = list(set(arr) - set(t1))

    s1 = 0
    for x, y in cb(t1, 2):
        s1 += arr[x][y]
    s2 = 0
    for x, y in cb(t2, 2):
        s2 += arr[x][y]
    
    ans = min(ans, abs(s1-s2))
print(ans)