AndroidTeacher

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

문제 설명

문제에서 n이 주어지고 1부터 n까지 차례대로 번호가 붙은 사람 n명이 존재한다.

이 n명의 사람을 두 팀으로 나눈 후 각 팀의 시너지의 합을 구하게 되는데

시너지는 문제에서 입력으로 주어진다.

n x n 형식의 배열로 주어지며 배열[1][2] 는 1과 2가 한팀일 때의 시너지를 나타낸다.

이 때, 두 팀의 시너지의 합의 최소값을 구하는 문제이다.

풀이 과정

이 문제는 두 팀의 시너지 차이의 최소값을 구해야 하므로 모든 시너지를 탐색해야 하는 브루트포스 문제이다.

따라서 다음과 같이 접근하였다.

① 조합(Combinations)을 이용해 모든 경우의 수(팀)를 구한다.

    n = 6 이면 6개 중에서 순서를 고려하지 않고 3개를 뽑는 경우의 수와 같다.

    그러면 팀 1 : [1, 2, 3] / 팀 2: [4, 5, 6] 등과 같이 팀을 구할 수 있다.

② 각 경우의 수에 대해 팀의 시너지를 구한다.

    위의 예시에서는, 팀1의 경우에는 graph[1][2] + graph[1][3] + graph[2][1] ... + graph[3][2] 를 구하고

    팀2의 경우에는 graph[4][5] + graph[4][6] + ... graph[6][5] 를 구하면 된다.

③ 두 팀의 시너지의 차이와 현재 최소값과 비교해

    현재 차이가 더 작다면 최소값을 현재 차이로 교체한다.

이를 파이썬 코드로 나타내면 다음과 같다.

from itertools import combinations

n = int(input())
graph = []
number = [i for i in range(n)]

minR = int(1e9)

for i in range(n):
    graph.append(list(map(int, input().split())))


for c in combinations(number, n//2):
    visited = [False] * n
    team1 = []
    team2 = []
    for i in c:
        visited[i] = True
        team1.append(i)

    for i in range(n):
        if not visited[i]:
            team2.append(i)

    sum1 = 0
    sum2 = 0
    for i in range(n//2):
        for j in range(n//2):
            if graph[team1[i]][team1[j]] != 0:
                sum1 += graph[team1[i]][team1[j]]
            if graph[team2[i]][team2[j]] != 0:
                sum2 += graph[team2[i]][team2[j]]

    if abs(sum1-sum2) < minR:
        minR = abs(sum1-sum2)

print(minR)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

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

문제 설명

666, 1666, 2666, 3666 ... 으로 수 들이 나열될 때

N번째 수는 어떤 수인지를 맞추는 문제이다.

풀이 과정

문제에서 주의해야 할 점은 6이 3번 나타나기 때문에 7번째 수는 6666이 아니라 6660이 되어야 한다. 

그리고 작은 수들부터 나열을 하기 때문에 8번째 수는 7666이 아니라 6661이 될 것이다.

이러한 조건들을 위해 조건문을 나열하기에는 너무 까다롭기 때문에

하나하나 직접 값을 비교하는 방법을 이용하자.

(N은 최대 10000이기 때문에 시간초과도 발생하지 않는다.)

666부터 시작하여 값을 1씩 더해가며

작은값부터 찾는 방식이다.

n = int(input())
a = 666
cnt = 0

while n:
    if "666" in str(a):
        n -= 1
    a += 1

print(a-1)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

programmers.co.kr/learn/courses/30/lessons/72411

문제 설명

문제에 대한 설명이 굉장히 길어 링크로 대체합니다.

주어진 orders중에 course 개수 만큼 코스요리로 재구성할 수 있는 메뉴들을 알파벳 오름차순으로 골라내면 됩니다.

풀이 과정

풀이 ①

딕셔너리를 이용하여, 메뉴를 구성할 수 있는 모든 경우의 수를 정리합니다.

각각의 경우에 대해 개수를 세어준 후에,

해당 케이스의 주문 횟수가 2회 이상이면서, 최댓값인 경우에 answer에 추가 합니다.

(문제에서, 각 course에 대해 가장 많이 주문된 것을 고르라고 했으므로. 단, 최댓값을 가지는 메뉴가 여러개일 경우 모두 나타내야 함)

마지막에 알파벳 순으로 정렬하여 나타내면 코드 완성입니다.

from itertools import combinations


def solution(orders, course):
    answer = []
    order_dict = {}

    for i in range(len(course)):
        for j in range(len(orders)):
            for c in combinations(orders[j], course[i]):
                cc = list(c)
                cc.sort()
                tmp = ''.join(cc)
                if tmp in order_dict:
                    order_dict[tmp] += 1
                else:
                    order_dict[tmp] = 1

    print(order_dict)
    for c in course:
        arr = []
        maxNum = 2
        for k, v in order_dict.items():
            if len(k) == c:
                if maxNum < v:
                    arr = [k]
                    maxNum = v
                elif maxNum == v:
                    arr.append(k)
        for i in range(len(arr)):
            answer.append(arr[i])

    answer.sort()

    return answer

print(solution(["XYZ", "XWY", "WXA"], [2,3,4]))

풀이 ②

파이썬의 내장모듈인 Counter를 이용합니다.

orders에 있는 모든 경우의 수를 order_list에 넣은 후에,

Counter를 통해 order_list의 각각 값들이 등장하는 횟수를 셉니다.

most_common() 메소드를 통해 빈도순으로 내림차순 정렬합니다.

그럼 order_list의 첫 번째 원소 order_list[0]의 두 번째 값 order_list[0][1]은 최대 횟수를 나타냅니다.

풀이 ①과 마찬가지로 주문 횟수가 2회 이상이면서, 최댓값인 경우에 answer에 추가 합니다.

from itertools import combinations
from collections import Counter


def solution(orders, course):
    answer = []
    for i in range(len(course)):
        order_list = []
        for j in range(len(orders)):
            for comb in combinations(sorted(orders[j]), course[i]):
                order_list.append("".join(comb))

        if order_list:
            order_list = Counter(order_list).most_common()
            maxCnt = order_list[0][1]

            for order in order_list:
                if order[1] == maxCnt and order[1] > 1:
                    answer.append(order[0])
                else:
                    break

        answer.sort()
    return answer

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

programmers.co.kr/learn/courses/30/lessons/12924

문제 설명

n이라는 숫자가 있을 때, 이 숫자를 연속된 수들의 합으로 나타낼 수 있는 가지 수를 구하는 문제이다.

예를 들어, n = 15이면

• 1 + 2 + 3 + 4 + 5 = 15
• 4 + 5 + 6 = 15
• 7 + 8 = 15
• 15 = 15

이렇게 나타낼 수 있으므로 n=15일 때의 정답은 4이다.

풀이 과정

일일이 확인해가며 해당 경우에 참인지 거짓인지를 판별해야 하는 문제이다.

일단, i = n인 경우에는 무조건 해당되므로 answer은 1부터 시작하며,

절반까지만 검사하면 된다.

예를 들어, n = 15일 경우 8이상부터는 어떤 수를 더하더라도 15를 넘기기 때문이다.

수들을 더해가며 n일 경우에만 count 를 하나씩 늘려주면 된다.

def solution(n):
    answer = 1
    for i in range(1, n // 2 + 1):
        stack = []
        for j in range(i, n + 1):
            stack.append(j)
            if sum(stack) >= n:
                break
        if sum(stack) == n:
            answer += 1

    return answer

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

www.acmicpc.net/problem/2292

문제 설명

위 링크의 문제에 나온 것 처럼, 입력 한 숫자가 들어있는 칸에 가기 위해서 1번 칸 부터 거쳐야 하는 칸의 수를 출력하면 된다.

풀이 과정

1번이 가운데 기준으로 첫 번째 주기라고 했을 때 1,

2번째 주기는 2~7

3번째 주기는 8~19

4번째 주기는 20~37

5번째 주기는 38~61

이렇게 나타나며 각 주기의 끝자리가 6의 배수처럼 늘어나는 것을 알 수 있다.

즉, 1->7->19->37->61 은 6->12->18->24 이렇게 늘어난다.

그래서 1번 거쳐야 하는 방의 수는 1개,

2번 거쳐야 하는 방의 수는 6개

3번 거쳐야 하는 방의 수는 12개

4번 거쳐야 하는 방의 수는 18개 ... 이런 식으로 규칙적으로 늘어나게 됨을 알 수 있다.

따라서 다음과 같이 코드를 작성할 수 있다.

1인 경우는 1개이며, 2인 경우부터 내가 찾고자 하는 숫자가 현재 바퀴의 최대값보다 작으면 그 바퀴에 있으므로

그 바퀴를 출력해주면 된다.

n = int(input())

cur = 1
plus = 6
circle = 1
if n == 1:
    print(1)
else:
    while True:
        cur += plus
        circle += 1
        if n <= cur:
            print(circle)
            break
        plus += 6

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !