실버 1 https://www.acmicpc.net/problem/4920

[Python]

풀이 방법:

테트리스 5가지를 블록 별로 구분

코드:

def find_max(arr, n, m):
    result = list()
    # ㅡ
    for i in range(n):
        for j in range(m-3):
            maximum = 0
            for k in range(4):
                maximum += arr[i][j+k]
            result.append(maximum)
    # ㅁ
    for i in range(n-1):
        for j in range(m-1):
            maximum = 0
            for k in range(2):
                maximum += arr[i+k][j+k]
            maximum += arr[i+1][j]
            maximum += arr[i][j+1]
            result.append(maximum)
    # N 대칭
    for i in range(n-2):
        for j in range(1, m):
            maximum = 0
            for k in range(2):
                maximum += arr[i+k][j]
            maximum += arr[i+1][j-1]
            maximum += arr[i+2][j-1]
            result.append(maximum)
    # T
    for i in range(n-1):
        for j in range(m-2):
            maximum = 0
            for k in range(3):
                maximum += arr[i][j+k]
            maximum += arr[i+1][j+1]
            result.append(maximum)
    # L 대칭
    for i in range(n-2):
        for j in range(m-1):
            maximum = 0
            for k in range(3):
                maximum += arr[i+k][j+1]
            maximum += arr[i+2][j]
            result.append(maximum)

    return max(result)
    
    
def rotate_90(arr, n, m):
	result = [[0 for j in range(n)] for i in range(m)]

    for i in range(m):
        for j in range(n):
            result[i][j] = arr[n-j-1][i]

    return result
    
    
def main():

    t = 1
    while True:
        n = int(input())
        if n == 0:
            break
        arr = list()
        for i in range(n):
            arr.append(list(map(int, input().split())))

        maximum = -999999999999999999
        maximum = max(maximum, find_max(arr, n, n))
        arr = rotate_90(arr, n, n)
        maximum = max(maximum, find_max(arr, n, n))
        arr = rotate_90(arr, n, n)
        maximum = max(maximum, find_max(arr, n, n))
        arr = rotate_90(arr, n, n)
        maximum = max(maximum, find_max(arr, n, n))

        print("{}.".format(t), maximum)
        t += 1

    return
    
if __name__ == '__main__':
    main()

실버 1 https://www.acmicpc.net/problem/3019 

[Python]

풀이 방법:

우선, 각 블록마다 회전하여 필드에 떨어트렸을때, 딱 맞게 떨어지는 필드의 높이를 숫자로 표현해본다.

1번블록

ㅣ : 한칸 넓이 이므로, 모든 경우에 가능. 즉 c만큼의 경우의 수. 

ㅡ : 넓이가 4이므로, 필드에서 4칸연속 높이가 같은 곳이 있는 경우의 수.  0000

2번블록

ㅁ : 넓이가 2이므로, 필드에서 2칸연속 높이가 같은 곳이 있는 경우의 수. 00

3번블록

넓이가 3인데 가장 오른쪽 아래를 보면 비어있으므로, 필드에서 2칸연속 높이가 같으면서 3번째칸은 높이가 1인 경우의 수. 001

넓이가 2인데 가장 왼쪽 아래를 보면 비어있으므로, 1번째칸은 높이가 1이면서 다음은 한칸 낮은 경우의 수.10

7번 블록까지 숫자로 표현한다.

블럭의 경우마다 나누어 for문으로 필드의 높이를 비교하여 ans를 증가해주면 된다.

• 각 블록마다 회전하여 필드에 떨어트렸을때, 딱 맞게 떨어지는 필드의 높이를 숫자로 표현
• 각 블록마다 회전하여 놓았을때 딱 맞을 수 있는 높이의 경우를 구해줌
• 그 경우에 해당하면 ans를 1씩 증가시킴

코드:

import sys
input = sys.stdin.readline

c,block = map(int,input().split())
fd = list(map(int,sys.stdin.readline().split()))

ans=0
if block == 1:
    #ㅣ모양의 블럭은 모든열에 놓을 수 있기 때문에 c만큼 경우의 수를 더함
    ans += c  #0
    for i in range(c-3):
        #0000
        if fd[i] == fd[i + 1] and fd[i + 1] == fd[i + 2] and fd[i + 2] == fd[i + 3]:
            ans+=1
if block == 2:
    for i in range(c-1):
        #00
        if fd[i] == fd[i + 1]:
            ans+=1
if block == 3:
    for i in range(c-2):
        #001
        if fd[i] == fd[i + 1] and fd[i + 1] == fd[i + 2] - 1:
            ans+=1
    for i in range(c-1):
        #10
        if fd[i] == fd[i + 1] + 1:
            ans+=1
if block == 4:
    for i in range(c-2):
        #100
        if fd[i] == fd[i + 1] + 1 and fd[i + 1] == fd[i + 2]:
            ans+=1
    for i in range(c-1):
        #01
        if fd[i] == fd[i + 1] - 1:
            ans+=1
if block == 5:
    for i in range(c-2):
        #000
        if fd[i] == fd[i + 1] and fd[i + 1] == fd[i + 2]:
            ans+=1
        #101
        if fd[i] == fd[i + 1] + 1 and fd[i + 1] == fd[i + 2] - 1:
            ans+=1
    for i in range(c-1):
        #10
        if fd[i] == fd[i + 1] - 1:
            ans+=1
        #10
        if fd[i] == fd[i + 1] + 1:
            ans+=1
if block == 6:
    for i in range(c-2):
        #000
        if fd[i]==fd[i+1] and fd[i+1]==fd[i+2]:
            ans+=1
        #011
        if fd[i]==fd[i+1]-1 and fd[i+1]==fd[i+2]:
            ans+=1
    for i in range(c-1):
        #00
        if fd[i]==fd[i+1]:
            ans+=1
        #20
        if fd[i]==fd[i+1]+2:
            ans+=1
if block == 7:
    for i in range(c-2):
        #000
        if fd[i]==fd[i+1] and fd[i+1]==fd[i+2]:
            ans+=1
        #110
        if fd[i]==fd[i+1] and fd[i+1]==fd[i+2] + 1:
            ans+=1
    for i in range(c-1):
        #02
        if fd[i]==fd[i+1]-2:
            ans+=1
        #00
        if fd[i]==fd[i+1]:
            ans+=1

print(ans)

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

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

[Python]

풀이 방법:

비내림차순이어야 한다. -> idx 로 range 조절

같은 수를 여러번 골라도 된다 -> visited 미사용

라고 생각해서 코드를 작성했으나 런타임에러 발생

런타임에러 코드:

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
lists = list(map((int, input().split())))
lists.sort()
out = []

def dfs(cnt, idx, n, m):
    if cnt == m:
        print(' '.join(map(str, out)))
        return
    
    temp = 0
    for i in range(idx, n):
        if temp != lists[i]:
            out.append(lists[i])
            temp = lists[i]
            dfs(cnt+1, i+1, n, m)
            out.pop()

dfs(0, 0, n, m)

def dfs(cnt, idx, n, m):
    if cnt == m:

cnt (= depth) 대신

def dfs(idx):
    if len(out) == m:

조건식으로 변경하였다.

수정 코드:

n, m = map(int, input().split())
lists = list(map(int, input().split()))
lists.sort()
out = []

def dfs(idx):
    if len(out) == m:
        print(' '.join(map(str, out)))
        return
    
    temp = 0
    for i in range(idx, n):
        if temp != lists[i]:
            out.append(lists[i])
            temp = lists[i]
            dfs(i)
            out.pop()

dfs(0)

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

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

[Python]

풀이 방법:

비내림차순 이야기가 없으므로 idx로 range 조절 안해도 된다.

같은 수를 여러 번 골라도 되니 (중복이 허용되니) visited 조건을 빼도 된다.

임시변수 temp를 사용한다.

코드 :

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
lists = list(map(int, input().split()))
lists.sort()
out = []

def dfs(cnt):
    # 중복 허용
    if cnt == m:
        print(' '.join(map(str, out)))
        return
    
    temp = 0
    for i in range(n):
        if temp != lists[i]:
            out.append(lists[i])
            temp = lists[i]
            dfs(cnt+1)
            out.pop()

dfs(0)

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

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• N개의 자연수 중에서 M개를 고른 수열
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

[Python]

풀이 방법:

비내림차순 조건이 붙었다면 idx로 range 조절을 해주면 된다.

코드 :

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
lists = list(map(int, input().split()))
lists.sort()
visited = [0 for _ in range(n)]
out = []

def dfs(cnt, idx, n, m):
    if cnt == m:
        print(' '.join(map(str, out)))
        return
    
    temp = 0  # temp 변수를 만들어서 전에 쓰인 변수 값과 비교
    for i in range(idx, n):
        if visited[i] == 0 and temp != lists[i]:
            visited[i] = 1  # 방문 처리
            out.append(lists[i])
            temp = lists[i]
            
            dfs(cnt+1, i+1, n, m)    
            out.pop()
            visited[i] = 0  # 방문 초기화  

dfs(0, 0, n, m)