기록

문제 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 풀이 첫번째 열에 속하는 두 값을 제외하고 연산을 시작한다. 제한사항에 따르면 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 함께 사용할 수 없다. 이 조건을 이용하여 왼쪽에서 오른쪽으로 진행하면서 max(왼쪽 대각선 값+현재 값, 왼쪽값)을 연산하였다. # 초기상태 [50, 10, 100, 20, 40] [30, 50, 70, 10, 60] # n = 1 [50, 50, 100, 20, 40] [30, 100, 70, 10, 60] #..

문제 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 풀이 N이 10이라고 할때, 경우의 수를 트리의 형태로 나열 할 수 있다. 같은 수가 다른 자리에서 여러번 등장할 수 있으므로 트리의 레벨 개념을 도입하였다. (N*level의 2차원 배열을 두었다고 생각할 수 있다.) 문제에서 N은 10^6보다 작은 자연수이므로, 메모리의 한계를 고려하여 defaultdict와 dict를 이용하여 아래의 코드처럼 표현하였다. 코드 from collections import defaultdict N = int(input()) tree = defaultdict(dict) # child: {lv:p} nums = [N] lv = 0 ..

문제 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net 풀이 " "를 "/"를 바꾸어 표현하면 아래와 같으며, 다음과 같은 패턴을 찾을 수 있다. 04: *(01)사이에 5개의 /가 들어가 있다. ****(03)의 길이는 5이다. 05: */*(02)사이에 3개의 /가 들어가 있다. */*(02)의 길이는 3이다. 06: ****(03)사이에 1개의 /가 들어가 있다. *(01)의 길이는 1이다. 07: *(01)사이에 11개의 /가 들어가 있다. *****/*****(06)의 길이는 11이다. 08: */* (02)사이에 9개의 /가 들어가 있다. */*///*..

문제 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 풀이 파이프가 움직일 수 있는 경우의 수를 stack에 넣고 빼내어 연산하였을 때 올바른 답을 얻을 수 있는 것을 확인하였다. 다만, 시간초과로 테스트케이스를 통과하지 못했다. N = int(input()) board = [list(map(int, input().split())) for i in range(N)] path = [(0, 1, 0)] # end point, 0:→, 1:↘, 2:↓ ans = 0 while path : r..

문제 1085번: 직사각형에서 탈출 한수는 지금 (x, y)에 있다. 직사각형의 왼쪽 아래 꼭짓점은 (0, 0)에 있고, 오른쪽 위 꼭짓점은 (w, h)에 있다. 직사각형의 경계선까지 가는 거리의 최솟값을 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 직사각형 내부의 임의의 점 (x, y)에서 직사각형 경계까지의 최소거리는 아래 네가지 값 중 가장 작은 값이다. 코드 x, y, w, h = map(int, input().split()) print(min(x, y, (w-x), (h-y)))

문제 1259번: 팰린드롬수 입력은 여러 개의 테스트 케이스로 이루어져 있으며, 각 줄마다 1 이상 99999 이하의 정수가 주어진다. 입력의 마지막 줄에는 0이 주어지며, 이 줄은 문제에 포함되지 않는다. www.acmicpc.net 풀이 읽어 들어온 숫자를 문자처럼 취급한다. 파이썬은 -1, -2처럼 인덱스를 처리할 수 있다. 이를 이용하여 가장자리 수부터 서로 비교해나간다. 코드 while True : num = input() if num=="0" : break else : ans = "yes" for i in range(int(len(num)/2)) : if num[-i-1]!=num[i] : ans = "no" break print(ans)

문제 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모� www.acmicpc.net 풀이 입력 문자열 w를 배열 ans에 넣는다. 마지막으로 넣은 문자가 패턴 p의 마지막 문자와 같고 ans의 크기가 p의 크기보다 크다면 패턴 p의 마지막 문자부터 ans를 검사한다. 검사 결과가 true일때 패턴 p의 길이만큼 ans.pop() ans에 저장된 문자들을 join연산으로 붙여서 프린트한다. ans의 크기가 p의 크기를 비교하는 조건이 없으면, 뒤에서부터 문자열을 검사하는 코드에서 ans의 길이가 p보다 작을때 인덱스를 벗어나..

문제 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 파이썬으로 작성한 코드는 시간초과로 테스트를 통과하지 못했다. N의 범위가 작다보니 정답 값을 리스트에 저장해서 통과하는 방법이 가능하다. 그 이외의 다른 방법을 찾지 못해 자바로 코드를 작성하였다. queen의 위치가 다음과 같을 때 [2, 4, 1, 3]처럼 저장할 수 있다. 1 1 queen 1 queen 2 2 2 3 3 3 queen 4 queen 4 4 후보자 n(1~N)은 arr의 각각의 원소에 대해 조건을 만족해야 한다. 1) 같은 행에 위치하지 않는다..