yoo.dev

문제 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 풀이 규칙을 먼저 찾았다. 1 -> 1 (1) 2 -> 2 (1+1, 2) 3 -> 4 (1+1+1, 1+2, 2+1, 3) 4 -> 7 (1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 1+3, 3+1, 2+2) 배열로 정리하면 다음과 같다 i 1 2 3 4 5 6 7 arr[i] 1 2 4 arr[1]+arr[2]+arr[3] arr[2]+arr[3]+arr[4] arr[3]+arr[4]+arr[5] arr[4]+arr[5]+arr[6] 그 후 최대 숫자가 11로 매우 작길래 11까지 배열을 미리 생성해두고 필요한 값만 출력했다. import s..

문제 11656번: 접미사 배열 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000보다 작거나 같다. www.acmicpc.net 풀이 import sys word = sys.stdin.readline().strip() dic = [] for i in range(len(word)): dic.append(word[i:]) for each in sorted(dic): print(each)

문제 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 풀이 브루트포스로 N*M하면 시간초과가 난다. 카운터를 사용해서 2개인 애들만 출력했다. import sys from collections import Counter N, M = map(int, sys.stdin.readline().split()) arr = [] for _ in range(N+M): arr.append(sys.stdin.readline().strip()) answer = [] coun = Counter(arr).most_common() ..

문제 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 결국 시간초과가 나서 pypy로 제출했다. import sys from collections import deque N, L, R = map(int, sys.stdin.readline().split(" ")) dr = [-1, 0, 1, 0] dc = [0, 1, 0, -1] land = [] for _ in range(N): land.append(list(map(int, sys.stdin.readline().split(" ")))) t ..

문제 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이 다이나믹 프로그래밍으로 풀 수 있는 문제 배열을 하나 만들어서 N까지 채워주는 방식으로 풀었다. 1부터 3까지는 0, 1, 1으로 채워주고 그 뒤부터는 3으로 나눈 값(나누어 떨어지는 경우), 2로 나눈 값(나누어 떨어지는 경우), 1을 뺀 값 세가지 중 가장 작은 값에 1을 더해서 배열에 넣어줬다. import sys N = int(sys.stdin.readline()) arr = [0, 0] for i in range(2, N+1): if i

문제 2961번: 도영이가 만든 맛있는 음식 첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 www.acmicpc.net 풀이 import sys from itertools import combinations N = int(sys.stdin.readline()) arr = [] for _ in range(N): arr.append(list(map(int, sys.stdin.readline().split(" ")))) com = [] for i in range(1, N+1): com.append(combinations(arr, i)) answer = 100..

문제 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 풀이 기본적인 bfs 탐색 문제에서 보통 상하좌우 4곳만 확인하는 부분을 대각선까지 8군데로 확장시켜주면 간단하게 풀 수 있는 문제다 import sys from collections import deque while True: # 지도의 너비와 높이 w, h = map(int, sys.stdin.readline().split(" ")) # 입력의 마지막 줄에는 0이 두 개 주어진다. if w == 0 and h == 0: break # 인풋 지도 받..

문제 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 풀이 하노이탑의 이동 횟수는 2^n -1 이며 하노이탑 이동 시뮬레이션은 함수로 따로 구현했다. 1번탑의 원반들을 3번탑으로 옮겨야할때 재귀적 방법으로 n개의 원반중 가장 아래 한개를 제외한 n-1개를 2번탑으로 옮긴 후, 남아있는 1개의 원반을 3번으로 옮기고 2번으로 옮겨둔 n-1개의 원반을 다시 3번 탑으로 옮기면 된다. import sys # num: 옮겨야하는 수 / f: from / b: 거쳐서 / t: to def hanoi(num,..