본문 바로가기

알고리즘 문제풀이/백준

 (25)
백준(boj) 13458_시험 감독 (파이썬, c++) https://www.acmicpc.net/problem/13458풀이시험을 봐야 하는데 총감독관 1명은 고정, 총감독관이 감시 가능한 인원 외 나머지 인원을 부감독관이 모두 감시할 수 있을 만큼 뽑아주면 된다. 계속 빼주면 너무 오래 걸리니 나누기 연산을 사용한다. 단, 나눴을 때 나머지가 0이 아니면 (예를 들어 남은 인원이 3명이고 부감독관 감시 능력이 2명이면 나머지가 생긴다. 이럴 땐 부감독관이 한 명 더 있어야 한다) 나눈 값에 1을 더해준다.python3from sys import* input = stdin.readline ​ n=int(input()) a=list(map(int,input().split())) b,c=map(int,input().split()) #총감, 부감 res=0 fo..
백준(boj) 3190_뱀 (파이썬, c++) https://www.acmicpc.net/problem/3190풀이뱀의 이동 방향과, 시간에 따른 방향의 변화가 주어진다. 뱀의 머리가 움직일 때 그 자리에 사과가 있으면 사과를 먹고 꼬리는 그대로 두고, 만약 사과가 없으면 머리를 움직이고 마지막 꼬리를 잘라낸다. 꼬리의 순서가 필요하므로 tail이라는 이름의 queue를 사용했다 . 시간에 따른 방향 변화도 큐에 넣고 제일 앞에 있는 원소의 시간이 현재 시간과 같으면 방향 지시에 따라 방향을 변화 시켜 주었다. 방향은 dd배열을 URDL순으로 만들어 놓고, 시계방향이면 dd배열의 다음 방향으로 바꾸고, 반시계방향이면 dd배열의 전(前) 방향으로 바꿔주었다.python3from sys import* from collections import* inpu..
백준(boj) 13460_구슬 탈출2 (파이썬, c++) https://www.acmicpc.net/problem/13460풀이빨간 구슬과 파란 구슬이 있다. 네 방향으로 기울일 수 있는데 한번 기울이면 구슬이 벽에 닿거나 구멍에 빠질 때까지 이동한다. 파란 구슬은 어떠한 상황에도 빠지면 안 되고, 빨간 구슬만 구멍으로 들어갔을 때 게임이 끝난다. 최소 몇 번 만에 빨간 구슬을 빼낼 수 있을까 찾는 문제이다. 단, 10번을 초과하면 -1을 출력한다. BFS를 사용해서 최단 거리를 찾아주었고, move() 함수를 통해 기울이는 동작을 구현했다. visit 배열을 4차원으로 선언해서 빨간구슬, 파란구슬 각각의 x, y 값이 위치한 곳에 방문 순서를 기록해 두었다.python3from sys import* from collections import* input = ..
백준(boj) 17070_파이프 옮기기1 (파이썬, c++) https://www.acmicpc.net/problem/17070풀이가로 방향일 때 (x, y+1), (x+1, y+1) 부분에 벽이 없으면 갈 수 있고,세로 방향은 (x+1, y), (x+1, y+1) 부분에 벽이 없으면 갈 수 있고,대각선 방향은 (x+1, y), (x, y+1), (x+1, y+1) 부분에 벽이 없으면 갈 수 있다.대각선 방향으로 갈 때는 옆,아래,대각선 모두 벽이 없어야 갈 수 있으므로 따로 처리해 주었다.(n-1, n-1)로 가는 모든 경우의 수를 구하는 문제이다. BFS를 사용하였다.python3#c++은 통과, python은 시간초과남 dp로 다시 풀기 from sys import* from collections import* input = lambda:stdin.readl..
백준(boj) 16637_괄호 추가하기 (파이썬, c++) https://www.acmicpc.net/problem/16637풀이수식이 문자열로 주어진다. 피연산자는 0~9인 정수이므로 홀수번째 인덱스는 수식이고 짝수 번째 인덱스는 숫자인 것을 이용했다. solve() 함수를 이용해 완전 탐색 해줬는데 check 리스트를 이용해서 그 자리에 해당하는 수식이 켜져 있는지 꺼져있는지 확인 후 계산해 주었다. 이때 계산은 deque를 사용해 주었다.python3from sys import* from collections import* input = lambda:stdin.readline().strip() def cal2(n1, op, n2): #연산 받아서 계산 if op == '+': return n1+n2 if op == '-': return n1-n2 if op..
백준(boj) 17825_주사위 윷놀이 (파이썬, c++) https://www.acmicpc.net/problem/17825풀이주사위 10개의 턴이 주어지는데, 이를 이용해서 최대 점수를 구하는 문제이다. 완전 탐색 하였다. 요점 1. 말 4개를 가지고 게임을 하는데, 2. 이미 말이 있는 곳은 갈 수 없다. 3. 각 칸에는 점수가 있고 4. 파란색 선이 있는 부분은 파란 방향으로, 그 외엔 빨간 방향으로 가야 한다. 해결책 1. horse 라는 리스트에 [방향, 인덱스]를 표현해서 해결 2. visit 리스트를 이용하여 해결 3. 판에 있는 점수들을 a리스트에 표현하여 해결(a리스트 방향에 따라 셋팅) 4. 방향(d 변수)이랑 인덱스(x 변수)로 빨간 방향 부분이면 거기로 향하게 함 a 리스트를 그림으로 표현하면 다음과 같다. python3from sys i..
백준(boj) 12100_2048 (파이썬, c++) https://www.acmicpc.net/problem/12100풀이상하좌우 4방향으로 이동을 할 수 있는데, 같은 값을 갖는 두 블록이 충돌하면 두 블록이 하나로 합친다. 단, 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐지지 않도록 한다. st=[] (스택의 역할을)라는 리스트와 idx(index의 역할을)라는 변수를 사용해서 구현했다. 비교하려는 idx값이 없으면 => 이전에 추가된 값이 없으므로 값만 추가해준다. idx는 그대로 둔다. 비교하려는 idx값이 있으면 => 이전에 추가된 값과 비교하고 idx를 1 올려준다. 만약 비교값이 같으면 합쳐지는 것이므로 두 배 해주고, 다르면 새로운 값을 추가해준다. 그렇게 최댓값을 구해야 하므로 완전 탐색 해준다. solve() 함수를 ..
백준(boj) 17822_원판 돌리기 (파이썬, c++) https://www.acmicpc.net/problem/17822풀이인접한 곳에 같은 숫자이면 지워주고, 같은 숫자가 없는 경우에는 숫자들을 평균이랑 비교하여 1을 더하거나 빼주는 문제이다.원판을 2차원 배열로 생각하면 크게 3가지 상황으로 나타낼 수 있다.1.가로로 인접한 경우2.세로로 인접한 경우3.가로로 인접하나 처음과 끝으로 떨어져 있는 경우(원판이라서 나타나는 특징) 인접한 곳에 같은 숫자가 있는 경우 visit배열에 표시해놓고 전부 살펴본 후에 체크되어 있는 숫자들을 지워주었다. (가로, 세로 둘 다 같은 숫자인 경우 먼저 지우면 원하는 값을 못 구하므로 다 돌리고 처리) 1, 2 번은 4방향 위치 배열을 만들고 이 배열을 이용해 탐색하면서 체크해 주었고, 3번은 나머지 연산을 이용하였다. ..

티스토리툴바