철갑이의 이모저모

문제 www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1≤N ≤64의 범위를 가진다. 두 번째 줄부터는 길이 N 의 문자열이 N 개 들어온다. 각 문자열은 0 또는 www.acmicpc.net 풀이 2630번 색종이 만들기 문제와 같은 유형이다. www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net [백준] 2630..

문제 www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 풀이 분할 정복 : 재귀적으로 자신을 호출하면서 그 연산의 단위를 조금씩 줄어가는 방식 첫 색상이 나머지 색상과 같은지 확인 후 틀린 것이 있으면, 틀린 구역을 다시 네 구역으로 나누어 다시 색상이 같은 것을 확인해주기 위해 재귀를 이용해서 풀었다. 재귀 호출시 들어가야하는 인수의 값이 헷갈려서 그림으로 시작점을 표시해보았다. 비슷한 문제 [백준] 1992번(쿼드트리) with ..

문제 www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 풀이 배열을 정렬한 후 itertools 라이브러리에서 combinations 이터레이터를 사용해서 문제를 풀었다. 그리고 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성이 되었는지 카운트 해서 결과를 도출했다. docs.python.org/ko/3/library/itertools.html#itertools.combinations itertools — 효율적인 루핑을 위한 이터레이터..

문제 www.acmicpc.net/problem/1793 1793번: 타일링 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 숫자 0 ≤ n ≤ 250이 주어진다. www.acmicpc.net 풀이 비슷한 문제 [백준] 11727번(2xn 타일링 2) with Python 문제 www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. w.. happylsm76.tistory.com 다른 점이라면 예제를 입력 받는 부분을 어떻게 처리해야하나 고민했다. www.acmicpc.net..

문제 www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 풀이 dp문제는 처음 풀어봐서 하나하나 그려서 규칙을 찾은 후 점화식을 구했다. 위의 그림과 같이 N이 3 이상 이면 N-1에서 2x1 타일이 붙고, N-2에서 1x2 타일 두 개, 2x2 타일이 한 개 붙는 규칙이 계속된다. 따라서, dp[n] = dp[n - 1] + dp[n - 2] * 2 dp[1]과 dp[2]를 미리 구해서 시작. 답 a = int(input()) dp = [0,1,3] for i in range(3, a + ..

문제 www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1≤N≤10,000), M(1≤M≤300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 풀이 시간초과가 나서 투포인터를 공부해 문제를 풀어보았다. 합이 M보다 작은 경우 end 1 증가 시키고, M과 같으면 카운트, M보다 커지면 start 값을 1 증가시킨다. (반복) 답 N, M = map(int, input().split(' ')) A = list(map(int, input().split(' '))) cnt = 0 x = 0 end = 0 for start i..

문제 18406번: 럭키 스트레이트 첫째 줄에 점수 N이 정수로 주어진다. (10 ≤ N ≤ 99,999,999) 단, 점수 N의 자릿수는 항상 짝수 형태로만 주어진다. www.acmicpc.net 풀이 len()으로 받아온 값의 자릿수를 구해주고 절반씩 나눠 누적값을 구해줬다. 누적값의 경우, 예를 들어 a에서 123402를 받아오면 ['1', '2', '3', '4', '0', '2']처럼 요소로 이루어진 리스트처럼 여겨지기 때문에 a[i]로 인덱싱해서 누적해주었다. 답 a = input() b = 0 c = 0 if len(a) % 2 == 0 : for i in range(0,len(a) // 2) : b += int(a[i]) for i in range(len(a) // 2, len(a)) : ..

문제 www.acmicpc.net/problem/1057 1057번: 토너먼트 김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 www.acmicpc.net 풀이 토너먼트 표를 그려서 규칙을 찾아 보았다. 김지민의 경우 8 -> 4 -> 2 -> 1 번째로 즉, 현재번호/2 + 0 로 표현할 수 있다. 임한수의 경우 9 -> 5 -> 3 -> 1 번째로 즉, 현재번호/2 + 1 로 표현할 수 있다. 짝수일 때 홀수일 때로 나누기엔 복잡해지는 것 같아 둘 다 (현재번호/2 + 현재번호/2의 나머지) 로 처리하였다. 답 import java.util.Scanner; pu..

문제 www.acmicpc.net/problem/8958 8958번: OX퀴즈 "OOXXOXXOOO"와 같은 OX퀴즈의 결과가 있다. O는 문제를 맞은 것이고, X는 문제를 틀린 것이다. 문제를 맞은 경우 그 문제의 점수는 그 문제까지 연속된 O의 개수가 된다. 예를 들어, 10번 문제의 점수�� www.acmicpc.net 풀이 O가 나올때마다 count 값을 누적해주고 result 배열에 저장 해준다. O가 안나오면 count를 0으로 초기화 한다. result 배열 값을 전부 더한 값을 arr에 넣어주고 출력. 좀 더 시간을 단축해볼 것. 답 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamRea..

문제 www.acmicpc.net/problem/2525 2525번: 오븐 시계 첫째 줄에 종료되는 시각의 시와 분을 공백을 사이에 두고 출력한다. (단, 시는 0부터 23까지의 정수, 분은 0부터 59까지의 정수이다. 디지털 시계는 23시 59분에서 1분이 지나면 0시 0분이 된다.) www.acmicpc.net 풀이 C를 받아 시와 분으로 나눠 각각에 더해준다. 더한 결과 값으로 B(분) 값이 60이 넘어가면 A(시)에 1을 더해주고, B(분)에 60을 뺀다. 23시 59분에서 1분이 지나면 0시 0분이 되는 부분을 처리하기 위해 A(시)가 24와 같거나 커지면 24를 빼준다. 아직 파이썬이 익숙하지 않음. 문제를 더 많이 풀어봐야겠다. 답 A, B = map(int,input().split()) C..