![]()
보실 분이 있으실지는 모르겠지만 열심히 구상한 테스트케이스들입니다..! # k값과 문자열을 구성하는 알파벳 개수가 같을 때 제대로 출력되는지 확인, 1 5 antatica 답 : 1 # 문자열을 구성하는 알파벳 개수보다 k값이 작은 경우 제대로 출력되는지 확인, 1 4 antatica 답 : 0 # 문자열을 구성하는 알파벳 개수보다 k값이 큰 경우 제대로 출력되는지 확인, ★ 이거때매.. 1 10 antatica 답 : 1 # 제대로 쪼개졌는지 확인, 3 5 antatica antaaatica antaaaaatica 답 : 3 # a,i,t,n,c 제대로 빠지고 잘 작동하는지 확인 3 5 antaxxxxtica antaltica antaltica 답 :0 # 위와 같음 3 6 antaxxxxtica an..
딱히 뚜렷한 방법이 생각이 나지 않았습니다.. 그래서 그냥 맨 처음 생각났던 '한번에 두개 해보자'로 풀기 시작했습니다. from sys import stdin input=stdin.readline dx,dy=[0,0,1,-1],[1,-1,0,0] n,m=map(int,input().split()) board=[list(input().rstrip()) for i in range(n)] vi1=[[0 for i in range(m)]for i in range(n)] vi2=[[0 for i in range(m)]for i in range(n)] coins=[] ans=11 for i in range(n): for j in range(m): if board[i][j]=='o': coins.append((j,..
![]()
검사해야 할 것들은 주어진 좌표의 가로줄, 세로줄 그리고 스도쿠 판을 9개로 나누었을때 속해있는 그 칸의 9개의 나머지 블럭들 이 3가지입니다. 사실 그냥 시간을 전혀 신경쓰지않는다면 간단하게 정답을 구할 수 있지만 문제의 경우는 다음이라고 생각했습니다. # 이것만 오래 안걸리면 나머지 다 맞을듯 ''' 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ''' 위의 테스트 케이스만 빠르게 해결할 정도라면 문제를 맞추는 것은 어렵지 않다고 생각했고, 이것으로 계속 테스트를 ..
백트래킹이 익숙하지 않아서 쉬운 문제랑 내주시는 문제 병행하면서 같이 풀어보고 있는데 아직은 어렵네요. 이번 문제는 다른 사람 풀이를 참고해서 풀었습니다! 풀이 방법 1. row, col, square 변수를 만들어서 각각의 숫자가 행, 열, 사각형에 존재하는지 체크합니다. 예시로 들자면 1행에 3이 존재하면 row[1][3] = true, 5열에 1이 존재한다면 col[5][1] = true이 되는 것입니다. 사각형도 마찬가지로 9x9 스도쿠를 가로 세로 3등분씩 하여 나눠진 사각형에서 0번째 사각형에 5가 존재한다면 square[0][5] = true가 되는 것입니다. 2. 재귀 종료 조건은 cnt가 81이 되는 것입니다. cnt가 81이 되면 sudoku 전체를 출력하고 프로그램을 종료합니다. 여기..
![]()
https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 이 코드만 있으면 동아일보 스도쿠의 왕이 될 것 같네요! 풀이는 인터넷을 참고해 다음 순서대로 구현했습니다. 1. 값이 0인 지점에 숫자를 대입하고(방문 표시), 행 / 열 / 해당 지점이 속한 3 * 3 공간에 1 ~ 9가 모두 들어 있는지 검사합니다. 2. 만약 모든 검사를 통과했다면 다음 0을 찾아 1단계의 검사를 반복합니다. 3. 만약 검사에 걸렸다면, 해당 지점의 숫자를 다시 0으로..
SAT 관련해서 찾아보니 막막해서 참고없이 정석대로 풀기는 포기하였습니다. 시간제한은 무려 2초, 만들 수 있는 x1,x2...xi의 배열의 최대 길이는 n번째 위치에 있는 xn이 가질수 있는 값은 2개 (0,1) 최대 크기 20인 배열의 경우의 수 2**20 = 약 100만개의 배열이 존재, 검사해야할 쌍(a,b)의 최대 개수는 100개 100만개의 배열에 100개의 쌍을 대입해서 비교하고 도중에 틀린 값이 있으면 더이상 비교를 진행하지 않으면 100*100만 1억번 안쪽으로 가능할 것이라 생각했습니다. 배열은 오직 0과 1만 가질수 있으므로 경우의 수에 해당하는 배열 만들기는 매우 간단했습니다. def make(word): if len(word)==n+1: sat(word) return for i i..
![]()
N과 M 2번 풀이를 참고해 완성할 수 있었습니다. 푸는 순서 1. 입력을 사전순으로 정렬합니다. 2. 백트래킹을 이용해 조합을 구현합니다. 3. 모음, 자음 수를 체크해 조건을 충족하는 경우에만 출력합니다. L, C = map(int, input().split()) characters = list(input().split()) characters.sort() password = [] visited = [0] * C def backtrack(depth, start): if depth == L: consonant = 0 vowel = 0 for word in password: if word == "a" or word == "e" or word == "i" or word == "o" or word == "u..
솔직히 백트래킹이나 완전탐색이 뭔지 대략적으로 느껴지긴 하지만 정확히 이게 ~다 라고 못하겠습니다.. 그냥 다 돌아본다 이런 느낌은 받고 있습니다. 이번 같은 경우는 dfs로 구현을 해보았는데 일단 입력받은 문자를 정렬시키고 사용할 문자의 인덱스값을 함수에 전달시켜줘서 무조건 이전 인덱스보다 뒤에, 즉 사전순으로 정렬되도록 하였습니다. 총 전달하는 값은 4개의 값을 전달시켜주었습니다. (현재 단어, 가장 마지막에 사용한 문자의 인덱스, 자음의 개수, 모음의 개수) 이렇게 4개를 전달시켜주었고, c와 단어의 길이가 같아지면 자음의 개수와 모음의 개수가 같다면 print하고 return 아니면 그냥 return 해주었습니다. 자음 모음 판별은 그냥 a e i o u가 들어간 리스트에 해당 스펠링이 들어있나 ..
이분 탐색 문제는 많이 안 풀어봐서 그런지 항상 볼 때마다 접근 방법이 확실하게 생각나지 않는 것 같습니다. 힌트 주신 거에서 or를 보지 못하고 우선순위 큐와 이분 탐색을 어떻게 같이 써야 되나 고민하느라 이상한 쪽에서 시간을 보냈습니다. 접근 방법 1. 좌표 사이 값의 최대가 최소가 되도록 만들어야 했기 때문에 우선은 사이 값이 큰 수부터 처리를 해주어야 한다고 생각했습니다.(우선순위 큐 사용) 2. 테스트 케이스에 따라서 좌표와 좌표 사이 중간에 휴게소를 세웠을 때 최소가 되지만 백준에서 예시로 들어준 테스트 케이스와 같이 좌표와 좌표 사이에 여러 개의 휴게소를 세워야 하는 경우도 있습니다. 이 부분 처리를 어떤 식으로 해줘야 할지 모르겠어서 올려주신 풀이를 참고하였습니다.(굉장히 참신했던 것 같아..
1.vector로 입력을 받고 순서대로 정렬 2. 구간 길이 구하기 ( 0 ~ L ) 사이의 모든 구간 포함 3. 구간의 길이와 그 구간 내의 구간 개수를 같이 저장해야 한 구간을 여러 번 나눴을 때 거리 계산 가능...? 4. 나눴을 때 소수 값이 나올 수 있다는 점 유의....(이거 때문에 총 8번 시도하게 됐다...) 처음 틀렸을 때 여러 케이스를 돌려보니 소수 값이 나온다는 것을 알게 됐다. 그래서 소수 값을 처리하기 위해 while(m--){ double maxlen = dist.top().first; int section = dist.top().second; dist.pop(); dist.push({(maxlen*section) / (section+1) , section+1}); } doubl..
제가 사용한 풀이는 다음과 같습니다. 1. n개의 휴개소 위치와 0(시작점)과 l(맨 끝)을 가지는 배열을 정렬시키면 0~l까지 휴게소 위치를 차례대로 알 수 있으므로 한 위치와 다음 위치의 차가 거리가 됩니다. 이렇게 n+1개의 원소를 갖는 배열을 통해 n개의 거리를 얻을 수 있었습니다. 2. 이제 거리를 우선순위 큐에 넣어주도록 했습니다. 이때 넣을 때는 파이썬은 낮은 값이 맨 앞에 오므로 튜플 형태로 (-1*거리,거리) 이런식으로 넣어줄 수 있습니다. 그리고 이후에 탐색에 사용할 값인 나뉘기 전의 거리값과 나눈 분모도 같이 넣어주었습니다. (-거리,거리,나누기 이전의 값,나눈 분모) 이런 형식으로 값을 저장할 것이고 맨 처음에는 나누기 이전의 값과 나눈 분모는 0을 넣어주었습니다. 3. 거리가 가장..
