Dalin's Archive

문제 보러 가기! 문제를 읽어보니 토끼가 정보섬에 올라간 이유는! 당근을 많이 주워 가기 위해서였다 ! 🥕🥕 토끼는 →, ↘, ↗ 방향으로만 이동할 수 있다. 정문으로 들어와서 쪽문으로 나가는데, 쪽문은 여러 개이고 a 쪽문을 지나서 b 쪽문으로 나가도 상관없다. 토끼가 섬에 있을 동안 얻을 수 있는 당근의 최대 개수를 구하는 문제였다! (쪽문으로 빠져나갈 수 없는 경우에는 -1을 출력한다) ㅠㅠㅠ 많이 틀리다가 맞았따.. ㅠㅠㅠㅠ 일단은 토끼가 정문으로 들어오는 것은 'R'로 표시되기 때문에, 그 위치를 찾았다. 그 후에는 그쪽보다 오른쪽인 지점들을 다 쭉~ 봐주었다. 그러면서 해당 지점일 때까지 얻을 수 있는 당근의 최대 개수로 업데이트했다. (그 지점으로 올 수 있는 방법은 →, ↘,..

문제 보러 가기! ㅎㅎ제목부터 재밌다. (TMI: 나도 젤다의 전설 바람의 숨결! 게임을 종종 한다 ㅎㅎ ) 전에 나는 평범한 다익스트라 문제만 풀어봤는데, 조금 응용한 문제를 풀어봐서 재밌었다. 시작하는 점이 정해져 있고(제일 왼쪽 위), 음의 간선이 없으니까 다익스트라가 가능하다. 다익스트라는 특정 노드에서 시작해서, 다른 노드로 가는 최단 경로를 각각 구해준다. 이 문제는 잃은 도둑 루피가 최소로 되도록! 0,0 점에서 N-1,N-1까지 이동해야 한다. 조금 주의할 것이 있다고 하면~ 1차원 리스트로 최단 경로 테이블을 만들기 위해서, i좌표와 j 좌표를 곱해서 만든 하나의 숫자로 인덱스 위치를 표현했다. 상하좌우로 갈 때도 그 하나의 숫자를 바꿔줘야 한다. (위: -N, 아래: N, 왼쪽: -1,..

문제 보러 가기! 가지치기 없이 그냥 DFS로 풀었다~ N의 범위가 작아서, 그냥 해도 되는 것 같다! 시간 복잡도는 3^9 * 10 인데, 계산하면 196,830. 1초 내에 충분히 계산될 수 있다. DFS로 하고 DFS에 history와 idx를 만들었다. idx는 1부터 N까지 어떤 숫자를 볼 차례인지 담당한다. idx가 N+1이 되면 숫자를 다 본 것이다. 이때 수식의 결과가 0이 되는지 체크하면 된다! idx가 N+1 미만일 때는, 매번 +, -, 공백(숫자 이어지는 것) 의 경우로 재귀를 돈다. 헷갈렸던 부분! 바로 바로 idx가 N+1될 때 출력하면 안되어서(ASCII 순서에 따라서 출력하라고 함), 되는 경우를 리스트에 넣었다가 정렬한 후에 출력했다. ㅠㅠㅠ 계속 '출력 형식이 잘못되었습니..

문제 풀러 가기! 재미있는.. 그리디 문제였다.. ^^ 일단 입력을 받는다. 0, 0 이 나올 때까지 받으니까 while을 이용했다. 혹시 몰라서 출발점과 끝점이 같으면 받지 않았고, 출발점이 음수이고 끝나는 점이 0 이하이면 받지 않았다. 그리고 정렬~ 출발점 빠른 순 -> 출발점이 같으면 끝나는 점이 빠른 순으로 정렬했다. 그 후에 그 상황에서 끝나는 점의 좌표(finish_idx)와 사용한 선의 개수를 0으로 초기화했다. 그리고 쭉~~ 봤다. 그러면서 finish_idx보다 일찍 시작하는 선분을 후보에 넣었다. 그리고 그 중에 끝나는 좌표가 제일 큰 선분을 사용하는 게 이득이니까! 제을 큰 끝나는 좌표를 finish_idx에 대입하고, 사용한 선의 개수를 1 더했다. 만약에 finish_idx가 M..

흑흑.. 스터디에서 누군가 비트 마스크 문제를 넣었는데, 전--혀 못 풀겠다. 하긴 나는 지금까지 백준에서 비트 마스크 문제를 단 하나밖에 안 풀었다..;; 그래서 쉬운 문제부터 풀려고 한다! (미완성입니다.ㅠ) 1094. 막대기 https://www.acmicpc.net/problem/1094 이건 비트 연산을 바로 쓴다기 보다는 비트를 이해하고 있나? 그런 문제 같다! 좀 생각해보면 이 숫자에서 2의 제곱수가 몇개 들어있나를 구하는 문제라는 걸 알 수 있다. bin()을 이용해서 풀었다. import sys input = sys.stdin.readline X = int(input()) binary_X = bin(X) print(binary_X.count('1')) 14936. 엘리베이터 장난 1052..

문제로 ~ 스터디에서 다른 분이 0-1 BFS를 설명해주셔서, 그걸 듣고 나서 구현했다~ !! 신기하다 ~!! 나는 큐에서 꺼낸 후에, 더 적은 거울 수로 이미 방문했으면 continue 하고 그 다음에 방문 체크(거울 수 업데이트)하는 부분에서 좀 헤맸다..! import collections import sys input = sys.stdin.readline direct = [(0, 1), (1, 0), (0, -1), (-1, 0)] W, H = map(int, input().rstrip().split()) INF = H * W + 1 arr = list(input().rstrip() for _ in range(H)) visited = [[INF] * W for _ in range(H)] # C 위..

문제 보러 가기! 항상 궁금했던 세그먼트 트리..! solved.ac에 태그를 보면, 다른 건 뭔지는 알겠는데 '세그먼트 트리'만 전혀 몰라서 궁금했다..!! 공부하고 싶어서 스터디 문제에 추가했고, 오늘 공부해봤다 ~~ 단순 배열에서 구간 합을 구하려면 O(N) 걸리는데, 세그먼트 트리를 사용하면 O(logN)으로 시간을 줄여준다 ! (꼭 구간 합을 구할 때만 사용하는 것은 아니고, 구간에서 최댓값이나 최솟값을 찾을 때도 사용한다고 한다.) 내가 세그먼트 트리에 관해서 쓰면 정말 좋겠지만,, 그건 미뤄두고 일단 뭘 참고했는지만 쓰겠다. 먼저 관련된 유튜브를 2개 정도 열심히 봤다! 그리고 아래 쪽 유튜브를 보면서 구현했다. 유튜브에서는 파이썬은 아니고 C?로 쓰신 것 같은데 설명을 듣고 주석을 달면서 ..

문제 풀러 가기! 주어진 예제 1을 풀이하면 아래 그림처럼 된다. ! dp - 모든 위치를 보면서 그 위치일 때 가장 큰 값을 저장했다. 일단 h가 0일 때는 tiles 값 그대로가 그 위치일 때 가장 큰 값이다. y좌표 1 이상이 될 때부터는.. 1) x좌표가 0이거나 w-1이면, y좌표가 현재 지점보다 1 적을 때 바로 위, 한쪽 대각선 중에(그림의 파란색 화살표들 참고) 큰 값을 택한다. 그 값과 tiles 자기 위치 값(그림에서 초록색 값)을 더한다. 2) x좌표가 1~ w-2라면, y좌표가 현재 지점보다 1적을 때 바로 위, 좌측 대각선 위, 우측 대각선 위 중(그림의 노란색 화살표 참고) 큰 값을 택한다. 그 값과 tiles 자기 위치 값(그림에서 초록색 값)을 더한다. y좌표가 h-1까지 오..

문제 풀러 가기 while을 열심히 써서 풀었다 ! while 안에 while을 써서 문제 푼 것은 오랜만인 것 같다~ 1.봐야할 챕터가 없을 때까지 쭉~ 본다. 2.30분 동안 볼 수 있는 챕터를 본다! 1) 남은 시간 미만으로 그 챕터를 다 볼 수 있는 경우 => 정답을 1 더하고, 남은 시간을 업데이트한다.(남은 시간 - 그 챕터 볼 때 걸리는 시간) 챕터 수도 1 늘려주고! 2) 남은 시간으로 그 챕터 절반 이상을 볼 수 있는데, 그렇다고 시간이 남지는 않는 경우 => 정답을 1 더하고, 봐야 할 챕터 수도 1 늘린다. 그리고 이제 다시 '2.30분 동안 볼 수 있는 챕터를 본다!'를 시작해야 하니까 break. 3) 남은 시간으로 그 챕터 절반 이상 볼 수 없는 경우. => 정답은..

문제로 가기 정렬하고 쭉 ~ 한번 보면 되는 스위핑 문제!! 정렬한 후에 (출발지가 앞쪽인 순서, 출발지가 같으면 도착지가 앞쪽일 수록 앞에) 쭉~ 보면서 두 노선씩 비교한다. a_route는 처음 노선으로 초기화하고 시작하고, b_route는 그 다음 노선부터 끝까지 쭉 본다. 만약 a, b 노선이 겹친다면 합쳐서 새로운 노선으로 만든다! 이때 요금은 더 낮은 쪽을 따른다. 출발점이 더 나중에어도, 도착점이 더 이른 노선이 있을 수도 있다. 노란 색 노선, 빨간 색 노선을 비교할 때는.. 일단 겹치니까 a_route를 업데이트하는데, 'a_route = (a_route[0], max(a_route[1], b_route[1]), min(a_route[2], b_route[2]))'에서 'max(a_rou..