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

 

1303번: 전쟁 - 전투

첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는

www.acmicpc.net

 

https://nodingco.tistory.com/138?category=516041 

 

[Java] 백준 1303번. 전쟁-전투 (실버1)

https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들..

nodingco.tistory.com

 

위 풀이의 Python 버전입니다. 크게 다를건 없고 Python이 코드라인이 훨씬 적습니다.

 

 

import sys
from collections import deque

nm = sys.stdin.readline().split(' ')
M = int(nm[0])
N = int(nm[1])
B, W = 0, 0
maps = []
delta = [[-1, 0],[1, 0],[0, -1],[0, 1]]

for n in range(N):
    maps.append(list(sys.stdin.readline()))

for n in range(N):
    for m in range(M):
        maps[n][m] = 0 if maps[n][m] == 'W' else 1

for n in range(N):
    for m in range(M):
        if maps[n][m] in [0, 1]:
            target = maps[n][m]
            count = 0
            queue = deque()
            queue.append([n, m])
            maps[n][m] = -1

            while len(queue) > 0:
                x, y = queue.popleft()
                count += 1

                for i in range(4):
                    nx = x + delta[i][0]
                    ny = y + delta[i][1]
                    if 0 <= nx < N and 0 <= ny < M and maps[nx][ny] == target:
                        queue.append([nx,ny])
                        maps[nx][ny] = -1

            count *= count
            if target == 0:
                W += count
            else:
                B += count

print(f"{W} {B}")
728x90

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

 

1026번: 보물

첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거

www.acmicpc.net

 

예전에 풀었던 문제들을 복습하면서 정리중입니다.

 

아이디어를 떠올리기 어렵지만 구현은 간단한 문제입니다.

A에 있는 수와 B에 있는 N개의 수를 하나씩 뽑아 곱해 더하고 그 누적합을 최소로 만드는 문제입니다.

 

해결방법은 간단합니다.

A에서 가장 작은수를 B에서 가장 큰수, 그 다음으로 작은 수를 다음으로 큰 수와 곱하는 식으로 계산해주면 됩니다.

문제의 조건에선 B를 재배열하지 말라고 하지만... 요구하는 정답이 A의 배열이었다면 몰라도 누적합이기 때문에 그냥 신경쓰지 않고 정렬해줘도 상관없습니다.

더보기

생각

예를 들어 2,8,1과 6,3,5가 입력으로 주어졌다고 가정해봅시다.
이를 각각 오름차순 내림차순으로 정렬하면 1,2,8과 6,5,3이 됩니다. 
문제의 정답은 앞에서부터 순서대로 두 집합의 수를 곱한 6 + 10 + 24 = 40이 됩니다.
6,3,5의 배열이 바뀌었지만 1,2,8과 6,5,3의 곱의 위치를 바꾸어 1,8,2와 6,3,5로 생각해도 답은 같습니다. 
그냥 적합한 순위의 수를 매번 찾기가 귀찮아 정렬해 놓았다고 생각해 버립시다.

 

 

아이디어가 맞는지 생각해 보겠습니다.

A에서 기존의 가장 작은 수를 a 라고 하면 a가 아닌 어떤 수는 a+c로 나타낼 수 있을겁니다. (a와 같을 수 있음, 즉 c≥0)

B에서 가장 큰 수를 b라고 하면 b가 아닌 어떤 수는 b-d로 나타낼 수 있을겁니다. (마찬가지로 d≥0)

아이디어가 틀리다면 다른 순서로 수를 배열했을때 합이 더 작아져야합니다.

 

다른 순서로 수를 배열한다면 기존의 (a * b) + ((a+c) * (b-d))가 (a * (b-d)) + ((a+c) * b)로 대체될겁니다.

 

각 식을 계산해 풀어주면 1. ab + ab + cb - ad - cd 와 2. ab - ad + ab + cb가 됩니다.

다른 수를 선택해서 합이 더 작아지는 케이스가 있다면 1번 식보다 2번 식이 더 작아야합니다.

즉 1번식 - 2번식 > 0 이 성립해야하는데, 계산해보면 cd < 0이 되고 c와 d는 각각 0 이상의 정수이기 때문에 성립하지 않습니다. (c와 d가 둘 다 0이라면 같은 크기일 순 있지만, 이때의 선택도 정답 조합의 하나가 됩니다.)

 

따라서 A에서 가장 작은 a와 B에서 가장 큰 b를 곱하는게 최소값이 되는 조합이고, 이렇게 fix된 a와 b를 제외한 A' B'로 다시 최소합을 구한다고 생각하면 같은 증명으로 A와 B의 크기가 1이 될 때까지 적용이 가능합니다. 

둘의 크기가 1이라면 당연히 곱할 수 있는 방법이 하나밖에 없겠죠.

 

따라서 위와같이 정렬된 A와 역정렬된 B를 순서대로 곱한 합이 최소값입니다.

 

(제가 수학전공이 아니기 때문에 증명은 틀릴 수 있습니다... )

 

n = int(input())
A = list(map(int, input().split(' ')))
B = list(map(int, input().split(' ')))

A.sort()
B.sort(reverse=True)

answer = 0

for i in range(0,n):
    answer += int(A[i]) * int(B[i])

print(answer)

 

 

728x90

문제풀이 루틴에 관한 글은
https://nodingco.tistory.com/23  <- 여기를 참고해주세요!

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

 

9084번: 동전

우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는

www.acmicpc.net



1. 이해 (5분) - 2분

01knapsack 유형의 문제입니다. 워낙 유명한 DP문제라 따로 설명은 하지 않겠습니다.

풀이방법은 간단합니다. 우선 어떤 동전의 값이 V이라고 하면 당연히 V금액을 만드는것이 가능합니다.

그리고 만약 M이라는 금액을 만드는 방법이 있다면 우리는 V짜리 동전 하나를 더해 간단히 M+V를 만들 수 있습니다.

2. 계획 (5분) - 2분

위에서 이해한 개념을 바탕으로 계획을 세워봅시다.

사용가능한 동전의 값들을 입력받고, 크기 M+1짜리 배열을 만듭니다.

우리는 이 배열에 0원부터 순차적으로 그 금액에 가능한 가짓수를 구하고 최종적으로 M원을 만들 수 있는 가짓수를 구할것입니다.

동전의 갯수 N만큼 반복해야하는 작업은 이렇습니다.

1. V짜리 동전을 가지고 금액 V를 만드는건 당연히 가능하다. (1가지 방법)

2. 만약 M이라는 금액을 만드는 방법이 X개 있다면, 그 X가지 방법에 V짜리 동전을 더해 M+V금액을 만들 수 있다. (X가지 방법) 

이 두가지 작업을 마치면 최종적으로 주어진 동전들로 M원을 만들 수 있는 방법의 수를 구할 수 있습니다.


3. 검증 (5분) - 1분

만약 중복조합같은 방식으로 문제를 풀려고 했다면 문제가 생겼겠지만, 구상한 방식에서 M짜리 배열의 크기는 1만에 불과하고 동전과 테스트케이스도 20,10개이므로 시간초과가 발생하지는 않을 것 같습니다.


4. 풀이 (30분) - 13분

파이썬을 사용했고 문제의 풀이방법만 알고 있다면 간단히 작성가능한 코드라 금방 끝났습니다.


5. 채점, 디버깅 (+5분)

첫 제출에서 런타임에러가 발생했습니다! 동전의 값어치와 금액 M 사이에 대소관계가 없어 발생한 Index에러였습니다.

(만약 만들 금액이 30원인데, 100원짜리, 500원짜리 동전을 사용하려고 하면..? DP배열의 index를 넘어간다!) 

동전의 값어치가 금액보다 클때 반복문을 통과하는 조건문을 만들어주어 통과했습니다.

 

import sys

T = int(sys.stdin.readline())
sb = ""

for t in range(T):
    N = int(sys.stdin.readline())
    coin = list(map(int, sys.stdin.readline().split(' ')))
    M = int(sys.stdin.readline())
    dp = [0] * (M + 1)

    for n in range(N):
        dis = coin[n]
        if(dis > M):
            continue
        dp[dis] += 1
        
        for i in range(dis+1, M+1):
            dp[i] += dp[i-dis]

    sb += str(dp[M]) + "\n"

print(sb)
728x90

문제풀이 루틴에 관한 글은
https://nodingco.tistory.com/23  <- 여기를 참고해주세요!

 

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

 

15810번: 풍선 공장

1, 2, 3번 스태프가 각각 5분, 7분, 3분씩 걸린다면 3분이 지났을 때 3번 스태프가 1개, 5분에 1번 스태프가 1개, 6분에 3번 스태프가 1개를, 7분에 2번 스태프가 1개를, 9분에 3번 스태프가 1개를, 10분에

www.acmicpc.net

 

 

 

JAVA로 푼 문제를 Python으로 다시 작성한 문제입니다.

풀이방법과 주의사항, JAVA 정답 코드를 보고 싶으신 분은 아래 링크를 확인해주세요!

https://nodingco.tistory.com/28

 

[JAVA] 백준 15810번. 풍선공장 (실버2)

문제풀이 루틴에 관한 글은 https://nodingco.tistory.com/23  https://www.acmicpc.net/problem/15810 15810번: 풍선 공장 1, 2, 3번 스태프가 각각 5분, 7분, 3분씩 걸린다면 3분이 지났을 때 3번 스태프가..

nodingco.tistory.com

 

 

 

 

import sys

N,M = map(int, sys.stdin.readline().split(' '))
staffs = list(map(int, sys.stdin.readline().split(' ')))

left = 0
right = min(staffs) * M

while(left+1 < right):
    center = (left + right)//2
    balloon = 0

    for n in range(N):
        balloon += center//staffs[n]
    
    if(balloon >= M):
        right = center
    else :
        left = center

print(right)
728x90

문제풀이 루틴에 관한 글은
https://nodingco.tistory.com/23  <- 여기를 참고해주세요!

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

 

10610번: 30

어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한

www.acmicpc.net



1. 이해 (5분) - 1분

문제에서 제시하는 조건은 30의 배수이지만, 사실상 3의 배수라고 생각을 해도 무방합니다.

3의 배수가 갖는 특징은 자릿수의 숫자를 모두 더하면 3의 배수가 나온다는 점입니다.

3, 6, 9, 12(3), 15(6)... 10진법에서 올림연산이 발생할때 3의 경우는 무조건 1만큼이 부족하기 때문에 앞의 자릿수는 1이 오르고 자기 자릿수에선 1만큼이 부족해지면서 합이 유지되는겁니다.

  

2. 계획 (5분) - 1분

문제에선 3의 배수가 아닌 30의 배수를 요구했으므로, 최소한 한개의 0이 필요합니다.

또한 가장 큰 수를 출력하라고 했으니 각 자리의 숫자들을 내림차순으로 정렬해 출력할 필요도 있겠네요.

다만 이 모든 계산은 이렇게 만들어진 수가 30의 배수일 경우, 즉 각 자릿수의 합이 3의 배수일 때만 해주면 됩니다.


3. 검증 (5분) - 1분

예외가 발생할 경우는 0 같은 특이한 수가 입력될때일텐데요, 조건에서 숫자가 0으로 시작하지 않는다고 하니 문제되지 않을것 같습니다.

각 자리의 숫자들을 내림차순으로 정렬한 수(만들 수 있는 가장 큰 수)도 3의 배수가 맞을까요?

예시를 떠올려보면 12345이나 54321이나 전부 3의 배수입니다! 각 자릿수의 합이 3의 배수기만 하면 전부 3의 배수인게 확실합니다.


4. 풀이 (30분) - 10분

오랜만에 Python을 사용하다보니 살짝 버벅였지만 작성에 크게 어려운 부분은 없었습니다.

짧은 코드인데도 시간이 꽤 걸렸네요.


5. 채점, 디버깅 (+@)

3의 배수가 갖는 특징을 알고 Python 언어를 알면 쉽게 풀 수 있는 문제여서 한번에 통과했습니다.

문제 풀이에는 총 15분 가량이 걸렸습니다.

 

정답코드입니다.

N = list(input())
N = sorted(N, reverse=True)

if N[-1] != '0' :
    print(-1)
else:
    sum = 0
    for i in N:
        sum += int(i)
    if sum % 3 != 0 :
        print(-1)
    else :
        print(''.join(N))
728x90

+ Recent posts