nice!

[백준 14501번] 퇴사 - Python으로 구현하기

문제 접근

• DP인지? 브루트포스인지?
• 입력값의 범위로 봐서 브루트포스로 해결 가능해 보인다.
• 해당 날짜에 상담을 진행하는 경우, 안하는 경우를 재귀적으로 구현하여 모든 경우를 다 보고 최대값만 뽑자

생각해볼 점

• dp로 어떻게 접근해야할지?

오답 분석

• 재귀 구현의 종료조건, 진행조건에 주의하기!

# 퇴사
n = int(input())
T = []
P = []
for _ in range(n):
    t,p=map(int,input().split())
    T.append(t)
    P.append(p)

ans = 0

# 종료 : index 가 n을 넘은 경우
# 진행 : index+t[i]가 n보다 작은 경우

def sol(index, profit):
    global ans

    if index > n:
        return
    if index == n:
        ans = max(ans, profit)
        return
    sol(index + 1, profit)
    sol(index + T[index], profit + P[index])

sol(0, 0)
print(ans)

* 틀린 부분이나 더 나은 방법이 있을 수 있습니다. 지적해주시면 감사하겠습니다!!

[백준 14500번] 테트로미노 - Python으로 구현하기

문제 접근

• 테트로미노가 되는 도형 5개를 제시해주었다.
• 해당 도형을 회전, 대칭시켜서 나올 수 있는 모든 경우의 수를 탐색하자

생각해볼 점

• 백트래킹으로 풀 수 있을 것 같다. 도전해보기!

오답 분석

• 좌표 계산 실수
• 단순 구현으로 문제를 접근 하는 경우 실수하면 찾기 힘드므로 집중하기!

# 테트로미노
n,m=map(int,input().split())
map_data = [list(map(int,input().split())) for _ in range(n)]

t1 =[[[0,0],[1,0],[2,0],[3,0]],
     [[0,0],[0,1],[0,2],[0,3]]]

t2 = [[[0,0],[0,1],[1,0],[1,1]]]

t3 =[[[0,0],[1,0],[2,0],[2,-1]],
     [[0,0],[0,-1],[1,0],[2,0]],
     [[0,0],[1,0],[2,0],[2,1]],
     [[0,0],[1,0],[2,0],[0,1]],
     [[0,0],[0,-1],[0,-2],[1,0]],
     [[0,0],[-1,0],[0,-1],[0,-2]],
     [[0,0],[-1,0],[0,1],[0,2]],
     [[0,0],[1,0],[0,1],[0,2]]]

t4 = [[[0,0],[1,0],[1,1],[2,1]],
      [[0,0],[0,1],[-1,1],[-1,2]],
      [[0,0],[1,0],[1,-1],[2,-1]],
      [[0,0],[0,1],[1,1],[1,2]]]

t5 = [[[0,0],[0,1],[0,2],[1,1]],
      [[0,0],[0,1],[-1,1],[1,1]],
      [[0,0],[0,1],[0,2],[-1,1]],
      [[0,0],[1,0],[2,0],[1,1]]]

all_case=t1+t2+t3+t4+t5
max_sum=0
for i in range(n):
    for j in range(m):
        for tet in all_case:
            tmp = 0
            for tet_pos in tet:
                nx,ny=i+tet_pos[0],j+tet_pos[1]
                if 0<=nx<n and 0<=ny<m:
                    tmp+=map_data[nx][ny]
                else:
                    break
            max_sum=max(max_sum,tmp)
print(max_sum)

* 틀린 부분이나 더 나은 방법이 있을 수 있습니다. 지적해주시면 감사하겠습니다!!

[백준 14499번] 주사위 굴리기 - Python으로 구현하기

문제 접근

• 주사위를 어떻게 자료구조로 표현하고 면 옮기기를 구현할 지가 관건
• 주사위의 각 면을 1~6번으로 부여 한 뒤 주사위가 굴러질 때마다 면을 바꿔주는 방식을 택했다.

생각해볼 점

• 기업 인적성에 나오는 정육면체 전개도 옮기기 구현?
• 면 옮기는데 좀 더 편하고 가독성 좋은 방법?

오답 분석

• 좌표 평면의 x,y와 문제의 x,y가 반대로 되어 있어서 틀린 사람이 많다.
• 항상 문제 꼼꼼히 읽기 주의!

# 1 index, n*m 인 borad
import sys
input = lambda: sys.stdin.readline().rstrip()

n, m, x, y, k = map(int, input().split())
dice=[0]*(6+1)
board = [list(map(int, input().split())) for _ in range(n)]  # 맵 정보
opers = list(map(int, input().split()))  # 동쪽은 1, 서쪽은 2, 북쪽은 3, 남쪽은 4로 주어진다.
direc = {1: (0, 1), 2: (0, -1), 3: (-1, 0), 4: (1, 0)}

for oper in opers:
    dx,dy=direc.get(oper)   # get pos

    # move next pos
    x+=dx
    y+=dy
    if 0<=x<n and 0<=y<m:   # 다음 좌표 이동가능
        # 주사위 면을 교체
        if oper==1: # 동쪽
            dice[3],dice[1]=dice[1],dice[3]
            dice[1],dice[4]=dice[4],dice[1]
            dice[4],dice[6]=dice[6],dice[4]
        elif oper==2:   # 서
            dice[4], dice[1] = dice[1], dice[4]
            dice[1], dice[3] = dice[3], dice[1]
            dice[3], dice[6] = dice[6], dice[3]
        elif oper == 3: # 남 : 5 6 2 1
            dice[5], dice[1] = dice[1], dice[5]
            dice[1], dice[2] = dice[2], dice[1]
            dice[2], dice[6] = dice[6], dice[2]
        elif oper == 4: # 북
            dice[2], dice[1] = dice[1], dice[2]
            dice[1], dice[5] = dice[5], dice[1]
            dice[5], dice[6] = dice[6], dice[5]

        if board[x][y]==0: # 칸이 0 이면 -> 주사위에 있는값이 복사됨
            board[x][y]=dice[6]
        else:   # 주사위 값 교체
            dice[6]=board[x][y]
            board[x][y]=0
        print(dice[1])

    else:   # 인덱스 오류 -> 해당 명령어 무시, 좌표 원상복귀
        x-=dx
        y-=dy

* 틀린 부분이나 더 나은 방법이 있을 수 있습니다. 지적해주시면 감사하겠습니다!!

[백준 13458번] 시험 감독 python으로 구현하기

문제 접근

• 각 방에 총감독관은 무조건 한명은 필요!
• 나머지 인원은 부감독관이 해결
• 하나의 시험장에 필요한 감독관 수 = 총감독관 1명 + 반올림((시험장 인원 - 총감독관 감시 가능 인원)%부감독관 감시 가능 인원)

생각해볼 점

• 시간복잡도 : 시험장의 수만큼 반복문이 돌아야 되므로 O(시험장 개수) 이다.

오답 분석

• 문제의 정답률이 낮은 원인을 Q&A에서 찾아보니 아래의 이유들이 대표적이다.
• 자료형 범위 초과
• 총감독관 혼자서 감시 가능한 경우 예외처리

# 시험 감독
# 응시생 모두 감시, 필요한 감독관의 수 최소값
import math
n = int(input())    # 시험장 개수
a = list(map(int,input().split()))  # 각 시험장 응시수
b,c = map(int,input().split())  # 총감독관 감시가능수, 부감독관 감시가능수

total_cnt=0
for i in range(n):
    # 총감독관
    res_ = a[i]-b if a[i]-b>0 else 0
    total_cnt+=1 + math.ceil(res_/c)
print(total_cnt)

* 틀린 부분이나 더 나은 방법이 있을 수 있습니다. 지적 해주시면 감사하겠습니다!!

[백준 3190번] 뱀 Python 으로 구현하기

• 삼성 SW테스트 초창기 문제라 그런지 최근 문제들에 비해 비교적 조건이 적은 편
• 주어진 조건들과 상황에 따라 그대로 코드로 옮기면 풀리는 시뮬레이션 유형의 문제
• 아래 코드는 list.pop(0) 와 oper.pop(0)의 시간복잡도를 고려하지 않은 코드

 * 해당 코드에서 Python의 list 대신 deque 를 쓰면 pop 연산의 O(n)의 시간복잡도를 O(1)로 바꿀 수 있다!

# 백준 3190번 - 뱀
n=int(input())	# 맵크기
k=int(input())	# 사과

# 맵
board=[[0]*(n+1) for i in range(n+1)]
# 사과 정보
for _ in range(k):
    x,y=map(int,input().split())
    board[x][y]=1

# oper
oper=[input().split() for _ in range(int(input()))]
snake=[(1,1)]    # snake 몸
# 끝나는 경우 -> 맵 밖에 나감 or 자신의 몸에 닿음
# 뱀은 처음에 오른쪽을 향한다.
d = [(0,1),(1,0),(0,-1),(-1,0)] # 동남서북
d_f=0
score=0	# 시간
x,y=1,1

while True:
    score+=1
    # 다음 x,y
    x+=d[d_f][0]
    y+=d[d_f][1]
    if 1<=x<=n and 1<=y<=n:
        snake.append((x,y)) # 몸길이 늘림
        for i in snake[:-1]: # 자기 몸과 부딪힌경우
            if (x,y)==i:
                print(score)
                exit(0)
        if board[x][y]==0: # 그냥 통로임-> 꼬리 삭제
            snake.pop(0)
        if board[x][y]==1:
            board[x][y]=0
    else:   # 맵을 나간 경우
        print(score)
        break

    if oper and score==int(oper[0][0]):
        if oper[0][1]=='D': # 오른쪽 90
            d_f= d_f+1 if d_f<3 else 0
            oper.pop(0)
        elif oper[0][1]=='L': # 왼쪽 90
            d_f = d_f - 1 if d_f > 0 else 3
            oper.pop(0)

* 틀린 부분이나 더 나은 방법이 있을 수 있습니다. 지적해 주시면 감사하겠습니다!