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

 

14888번: 연산자 끼워넣기

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 부호에 해당하는 리스트를 따로 만든 후 해당 리스트에서 보호의 순사가 바뀜에 따라 값도 바뀌게 되므로 순서가 중요한 순열로 뽑아야 합니다. 따라서 숫자의 경우 num이라는 리스트를 만들어 넣어주고 부호의 경우 따로 x라는 리스트를 만든 후 permutations를 통해 숫자보다 하나 적게 뽑은 후 ( 3 + 3처럼 부호의 경우 숫자보다 하나 적어야 함) 교차하여 부호와 숫자가 모두 포함이 된 리스트를 만든 후 이를 계산하는 calc함수를 구현하면 쉽게 해결할 수 있습니다.

문제 해결을 위한 팁

저의 경우 isdigit()를 통해서 부호와 숫자를 합쳐진 리스트에서 구별했는데 이때 int형애는 isdigit()을 사용할 수 없기 때문에 str을 이용하여 우선 다 문자 형태로 바꿔준 후에 isdigit()을 이용하였습니다.

소스코드

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
from itertools import permutations
 
def calc(arr):
  prev = int(arr[0])
  for i in range(1, len(arr)-1):
    if arr[i].isdigit() == False:
      if arr[i] == '+':
        prev += int(arr[i+1])
      elif arr[i] == '-':
        prev -= int(arr[i+1])
      elif arr[i] == '//':
        if prev >= 0:
          prev = prev // int(arr[i+1])
        else:
          prev *= -1
          prev = prev // int(arr[i+1])
          prev *= -1
      elif arr[i] == '*':
        prev *= int(arr[i+1])
  return prev
 
N = int(input())
num = list(map(int, input().split()))
numOfA, numOfB, numOfC, numOfD = map(int, input().split())
 
x = []
while True:
  if numOfA > 0:
    x.append('+')
    numOfA -= 1
  if numOfB > 0:
    x.append('-')
    numOfB -= 1
  if numOfC > 0:
    x.append('*')
    numOfC -= 1
  if numOfD > 0:
    x.append('//')
    numOfD -= 1
  if numOfA == 0 and numOfB == 0 and numOfC == 0 and numOfD == 0:
    break
 
maximum = int(1e9)*-1
minimum = int(1e9)
 
for xx in list(permutations(x, N-1)):
  j = 0
  arr = []
  for i in range(N-1):
    arr.append(str(num[i]))
    arr.append(str(xx[j]))
    j += 1
  arr.append(str(num[-1]))
  result = calc(arr)
  maximum = max(maximum, result)
  minimum = min(minimum, result)
 
print(maximum)
print(minimum)
 
 cs

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 16234: 인구이동(Python)  (0) 2020.12.07
백준 알고리즘 18428: 감시 피하기(Python)  (0) 2020.12.05
백준 알고리즘 18405: 경쟁적 전염(Python)  (0) 2020.12.05
백준 알고리즘 14502: 연구소(Python)  (0) 2020.12.05
백준 알고리즘 18352: 특정 거리의 도시 찾기(Python)  (0) 2020.12.04

 

 

15686번: 치킨 배달

크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸

www.acmicpc.net

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

문제

문제 해결을 위한 과정

이 문제의 경우 가장 중요했던 것은 조합 즉 combination을 이용하는 것이었습니다. 만일 a, b, c, d, e라는 5개의 치킨집이 있을 때 3개를 뽑는 경우라면 a, b, c와 a,c,b와 b,a,c와 b,c,a 등등 이렇게 뽑은 것이라면 같은 경우입니다. 즉 순서가 중요하지 않은 조합을 이용하여 해결하는 것입니다. 파이썬에서 조합을 사용하기 위해서는 다음의 코드를 추가합니다.

from itertools import combinations

이 방법을 통해 치킨집들중 입력받은 M개를 고른 후 각각의 집마다 치킨 거리를 구한 후 도시의 최소 치킨 거리를 구하면 됩니다.

문제 해결을 위한 팁

None

소스코드

town.append(list(map(<span

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
from itertools import combinations
 
def compute(data):
  answer = 0
  for i in range(len(house)):
    a, b = house[i]
    temp = int(1e9)
    for x, y in data:
      temp = min(temp, abs(x - a) + abs(y - b))
    answer += temp
  return answer
 
N, M = map(int, input().split())
town = []
house = []
store = []
 
for i in range(N):
  town.append(list(map(int, input().split())))
  for j in range(N):
    if town[i][j] == 1:
      house.append((i, j))
    elif town[i][j] == 2:
      store.append((i, j))
 
ans = int(1e9)
for data in combinations(store, M):
  ans = min(ans, compute(data))
 
print(ans)
 
 
 cs

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 14502: 연구소(Python)  (0) 2020.12.05
백준 알고리즘 18352: 특정 거리의 도시 찾기(Python)  (0) 2020.12.04
백준 알고리즘 3190: 뱀(Python, c++)  (0) 2020.11.29
백준 알고리즘 1914: 하노이 탑  (0) 2020.11.28
백준 알고리즘 18406: 럭키 스트레이트 (Python)  (0) 2020.11.27

 

 

3190번: 뱀

 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임

www.acmicpc.net

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

문제

문제 해결을 위한 과정

가장 먼저 주의해야 할 점은 보드의 맨 위 좌측의 좌표가 0행 0열이 아닌 1행 1열이라는 점입니다. 따라서 사과의 위치를 입력을 받은 후 일반적으로 사용하는 행, 열의 위치에 사과를 저장하기 위해 입력된 좌표에서 각각 1씩 빼서 보드에 사과를 집어넣어야 합니다. 단순하게 문제의 조건을 따라만 가면 그다지 어려운 문제는 아닙니다. 뱀이 바라보는 방향을 기준으로 한 칸씩 이동을 하게 되는데 몸길이가 늘려 머리가 다음칸에 가게 됩니다. 다음칸이 벽이거나 꼬리가 있는 부분이 아닌 한 머리가 속한 칸이 사과가 없는 칸이면 꼬리가 한 칸 앞으로 이동을 해야 합니다. 따라서 뱀이 현재 위치한 좌표들로 리스트를 만든 후 뱀이 머리가 닿는 부분을 리스트에 append 하게 되면 반대로 꼬리의 부분은 리스트의 맨 앞부분일 것입니다. 따라서 해당 리스트의 맨 앞을 pop 해주게 되면 쉽게 꼬리를 한 칸 앞으로 이동해줄 수 있습니다. 비록 리스트의 pop이 O(N)의 시간 복잡도를 가지더라도 이 문제에서는 통과할 수 있습니다. 

문제 해결을 위한 팁

이 문제를 풀때 신경 써야 할 부분은 바로 방향에 관한 부분입니다. 보통 방향에 관한 부분이 문제에서 나오면 dx, dy로 각각의 방향 리스트를 만드는 것이 일반적입니다. 맨 처음 뱀이 바라보고 있는 부분이 오른쪽 즉 동쪽이기 때문에 동쪽을 리스트의 0번째 리스트로 입력을 한 후 반 시계 방향으로 동쪽, 북쪽, 서쪽, 남쪽으로 방향을 설정하면 dx, dy는 다음과 같습니다.

dx = [0, -1, 0, 1]

dy = [1, 0, -,1 0]

이 좌표는 수학적 의미의 x, y좌표가 아닌 프로그래밍에서의 행, 열의 의미입니다. 동쪽 즉 오른쪽으로 움직이는 경우 행은 그대로지만 열이 하나 증가하기 때문에 dx, dy의 0번째 인덱스가 0, 1 입니다. 이렇게 하면 기존의 좌표를 x, y 다음 과표를 nx, ny라 지정하면 

nx = x + dx[0]

ny = y + dy[0]

이처럼 지정할 수 있습니다. 이번엔 표를 보고 생각해봅시다.

방향(리스트에서의 인덱스 값) D 인 경우(리스트에서의 인덱스 값) L 인 경우(리스트에서의 인덱스 값)
동쪽(0) 남쪽(3) 북쪽(1)
북쪽(1) 동쪽(0) 서쪽(2)
서쪽(2) 북쪽(1) 남쪽(3)
남쪽(3) 서쪽(2) 동쪽(0)

위 표를 보고 기존 방향이 dir일 경우 다음과 같음을 알 수 있습니다.

D인 경우 dir = (dir - 1) % 4

L인 경우 dir = (dir + 1) % 4 

소스코드 - python

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
N = int(input())
graph = [[0]*N for _ in range(N)]
apple = int(input())
movement = []
for i in range(apple):
  a, b = map(int, input().split())
  graph[a-1][b-1] = 1 # 문제에서 맨 좌측 위가 1, 1 이라고 하였기 때문
 
move = int(input())
for i in range(move):
  a, b = input().split()
  movement.append((int(a), b))
 
# 동, 북, 서, 남
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]
 
def turn(dir, x): # 다음 방향을 정하는 함수
  if x == 'D':
    dir = (dir -1) % 4
  elif x == 'L':
    dir = (dir+1) % 4
  return dir
 
def game():
  x = 0; y = 0
  graph[x][y] = 2 # 맨 처음 뱀이 0, 0 에 있으므로 해당 지역을 뱀이 있는것으로 표시
  snake = [(x, y)] # 뱀의 현재 좌표를 담는 리스트
  count = 0
  dir = 0 # 맨 처음 방향인 동쪽을 0으로 설정
  index = 0
  while True:
    nx = x + dx[dir]
    ny = y + dy[dir]
    if 0 <= nx < N and 0 <= ny < N and graph[nx][ny] != 2:  # 벽이 아니거나 뱀이 있는 지역이 
      if graph[nx][ny] == 0: # 사과 없는 지역인 경우
        count += 1
        graph[nx][ny] = 2
        snake.append((nx, ny))
        prev_x, prev_y = snake.pop(0)
        graph[prev_x][prev_y] = 0
      elif graph[nx][ny] == 1: #사과 있는 지역
        count += 1
        graph[nx][ny] = 2
        snake.append((nx, ny))
      if index < move and count == movement[index][0]:
        dir = turn(dir, movement[index][1])
        index += 1
      x = nx
      y = ny
    else:
      return count
 
print(game()+1)
 cs
소스코드 - c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <bits/stdc++.h>
#define MAX 101
 
using namespace std;
int n, k;
int graph[MAX][MAX];
int l;
queue<pair<int, char>> dir;
queue<pair<int, int>> snake;
int direction;
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };
 
int moveDirection(int direction, char dInfo) {
    if (direction == 0) {
        if (dInfo == 'L')
            return 2;
        else
            return 3;
    }
    else if (direction == 1) {
        if (dInfo == 'L')
            return 3;
        else
            return 2;
    }
    else if (direction == 2) {
        if (dInfo == 'L')
            return 1;
        else
            return 0;
    }
    else {
        if (dInfo == 'L')
            return 0;
        else
            return 1;
    }
}
 
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    cin >> k;
    for (int i = 0; i < k; i++) {
        int a, b;
        cin >> a >> b;
        graph[a - 1][b - 1] = 1;
    }
 
    cin >> l; 
    for (int i = 0; i < l; i++) {
        int a;
        char c;
        cin >> a >> c;
        dir.push(make_pair(a, c));
    }
 
    int time = 1;
    direction = 3;
    int xPos = 0, yPos = 0;
    graph[xPos][yPos] = 2;
    snake.push(make_pair(xPos, yPos));
    int tInfo = dir.front().first;
    char dInfo = dir.front().second;
    dir.pop();
 
    while (true) {
        xPos += dx[direction];
        yPos += dy[direction];
        if (xPos < 0 || yPos < 0 || xPos >= n || yPos >= n) {
            break;
        }
        if (graph[xPos][yPos] == 2) {
            break;
        }
        snake.push(make_pair(xPos, yPos));
        if (graph[xPos][yPos] != 1) { // 사과없는 경우
            int x = snake.front().first;
            int y = snake.front().second;
            graph[x][y] = 0;
            snake.pop();
        }
        if (graph[xPos][yPos] == 0) { // 사과 있는 경우
            graph[xPos][yPos] = 0;
        }
        graph[xPos][yPos] = 2;
        if (time == tInfo) {
            direction = moveDirection(direction, dInfo);
            if (!dir.empty()) {
                tInfo = dir.front().first;
                dInfo = dir.front().second;
                dir.pop();
            }
        }
        time++;
    }
    
    cout << time;
    return 0;
}
 cs

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 18352: 특정 거리의 도시 찾기(Python)  (0) 2020.12.04
백준 알고리즘 15686: 치킨 배달 (Python)  (0) 2020.11.30
백준 알고리즘 1914: 하노이 탑  (0) 2020.11.28
백준 알고리즘 18406: 럭키 스트레이트 (Python)  (0) 2020.11.27
백준 알고리즘 1439: 뒤집기 (Python)  (0) 2020.11.25

+ Recent posts

티스토리툴바