Dalin's Archive

[문제 보러 가기](https://www.acmicpc.net/problem/14940 평범한 BFS 문제였다. visited를 만들어서 방문 체크 겸, 거리 체크를 했다. 처음에는 '원래 갈 수 없는 땅인 위치는 0으로 출력'해야 하는데, 원래 갈 수 없는 땅이고 도달할 수 없는 위치면 -1로 출력해서 틀렸다. 그리고 i, j 오타가 나서 틀리다가 맞았다..! i, j.. 비슷하게 생겨서 주의해야 겠다. import collections import sys input = sys.stdin.readline MIIS = lambda: map(int, input().split()) directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] n, m = MIIS() a..

문제로~ RGB거리 1을 풀고, RGB 거리 2도 있길래 스터디 문제에 넣었다. RGB 거리 1은 괜찮았는데,,, 이 문제는 좀 더 생각을 해야 한다. 달라진 거라고는 1번 집 색깔과 마지막 집 색깔이 달라야 한다는 것 뿐이다. 그런데 훨씬 어렵다..ㅠ 아이디어가 잘 안떠올랐다.. 1번 집의 색깔을 기억(?)하고 있어야 한다는 거니까, R, G, B 각각에서 출발해 보면 된다. 또 첫번째 집과 마지막 집 색깔이 달라야 하니까, 정답(ans)을 구할 때 마지막 집을 R, G, B로 색칠한 결과(첫번째~마지막 집 색칠한 최소 비용) 중 첫번째 집과 색깔이 같은 건 고려하지 않아야 한다. R, G, B 각각에서 출발하는 것을 구현하려면.. => 다른 곳의 값은 크게 두고, 해당 색깔으로 칠하는 경우만 그 때 ..

문제 보러 가기 많이 틀리다가 맞았다!!! 틀렸던 이유 🙆‍♀️ 시작 정점 1에서 시작하지 않는 경우도 들어올 수도 있는 것을 체크하지 않았다. 단순히 깊이가 같은 것만 체크하면 안된다. 진짜 큐처럼, 순서도 고려해야 한다. 2에 대해서 좀 더 설명하겠다. 처음에는 깊이만 같으면 다 되는 줄 알았다..! 그래서 딕셔너리를 이용해서 각 깊이 별로 자식을 저장했다. 깊이 1일 때: 1 깊이 2일 때 : 2, 3, 4 깊이 3일 때: 5, 6, 7 입력으로 주어진 BFS 방문 순서를, 각 깊이에 있는 요소들의 길이만큼씩 잘라서 둘다 set으로 만들었다. 두 set이 같은지 판단했다. 이렇게 했더니 50%정도에서 틀렸다. 만약에 1-> 3-> 4-> 2가 들어왔으면, 3의 자식들, 4의 자식들, 2의 자식들 순..

문제로 가기 접근 🌰🍂 DP로 풀었다. 어떤 색으로 집을 칠할지, 몇 번째 집인지를 담은 2차원 리스트를 만들었다. 1번 집은 그냥 칠하면 된다. 그 이후 집들은 그 이전 집 색깔과 겹치지 않게 최소 비용으로 칠했다. 예를 들어, 현재 집을 빨강으로 칠할 때의 최소 비용을 구해야 하는 경우를 생각해보자. 그 이전 집이 초록일 때, 파랑일 때 최소 비용 중 싼 것을 택하고, 현재 집을 빨강으로 칠하는 비용을 더해서 dp 테이블을 채웠다. 코드 👩‍💻 import sys input = sys.stdin.readline N = int(input()) house_color_costs = list(list(map(int, input().split())) for _ in range(N)) dp = [[0] * 3 ..

문제 보러가기 접근 🍁 쭉~ 입력을 받은 후에 정렬을 했다. 정렬을 하는 게 매우 중요하다..!! start와 end는, 다른 선들과 겹치지 않는 선은 계산을 끝내고, (다른 선들과 겹칠 가능성을 가진) 당시에 가장 긴 선을 의미한다. 맨 처음 시작점, 도착점을 각각 start, end에 대입했다. 그 다음부터 각각의 시작점, 도착점과 start, end를 비교해 보면 아래 그림의 세 가지 경우 중 하나가 된다. (정렬을 했으니까 항상 그 시점의 시작점보다 start가 작거나 같을 것이다. 그래서 아래 세 가지 경우만 있다.) 1) 두 선이 겹치고, 그 때 꺼낸 도착점이 end보다 뒤에 있는 경우. 그러면 start는 그대로 두고, end는 그때 꺼낸 도착점으로 업데이트한다. 2) 두 선이 겹치고, 그 ..

문제 보러 가기! 문제를 꼼꼼히 읽고 구현하려고 했다~ 큐를 하나 만들어서 은행 대기 줄을 구현했다. 이미 줄 서있는 사람들은 이 큐에 넣고 시작했고, 나중에 오는 사람들은 시간이 될 때 큐 안에 넣었다. 1. 큐의 맨 앞에 있는 고객을 만나기 2. 고객 업무 처리하기 1) 고객에게 필요한 시간이 T보다 크거나 같으면 T초 동안 그 고객을 만났다. 시간을 1초씩 움직이면서, 그 고객 아이디를 출력했고, 만약에 그때 은행에 들어온 고객이 있는지 체크하고 있으면 큐 안에 넣어주었다. => 다 끝난 후에, 고객이 다시 뒤에 가서 서야 하면(필요한 시간이 T보다 컸으면) 큐의 맨 뒤에 넣었다. 2) 고객에게 필요한 시간이 그보다 작으면 필요한 시간만큼만 고객을 만나면 된다. 이때도 시간을 1초씩 움직이면서, 그..

문제로 가기 문제 소개, 아이디어 정훈이 -> 상대방의 순서로 카드를 윗장부터 하나씩 분배하고 있다. 카드 합이 더 큰 사람이 이긴다. 밑장 빼기를 최대 1번 해서, 정훈이가 얻을 수 있는 최대 카드 합을 구하는 문제이다. 밑장 빼기 최대 1번이니까 할 수도 있고, 안 할 수도 있는 것이다. 일단 안할 때 정훈이가 얻는 카드 합을 구했다. 그걸 ans에 대입했다. 그리고 밑장을 뺄 경우를 따져보면서, 각각의 상황에서 정훈이가 얻는 카드 합을 ans과 비교해서, 클 때의 값을 ans에 넣었다. 그러면 밑장 뺄 때 정훈이가 가진 카드의 합이 어떻게 되는지는 어떻게 구했을까? 일단 그림을 그려봤다 ! 정훈이 차례에 밑장을 빼면, 그 때를 포함해서 이후의 원래 상대가 가질 예정이었던 카드의 합과 정훈이가 가질 ..

와아아~~~ 이 문제를 풀어서 편안하게 잠잘 수 있겠다 ㅎㅎ 처음에는 메모리 초과 해결하느라고, 나중에는 게임 종료 후 빈 문자열이면 EMPTY 출력하는 걸 깜박해서 많이 틀렸다.. 문제 보러 가기 아이디어 카드의 갯수, 사람의 수가 최대 9..!! 사람들이 어떤 순서로 카드를 낼 수 있는지를 순열로 구했다. 각 순열대로 했을 때의 결과를 리스트로 저장했고, 사전순으로 출력이니까 정렬을 한 후에 출력했다. 같은 결과가 나오면 하나로 출력하라고 해서, set을 이용했다. (set에 저장한 후에 마지막에 리스트로 바꿔서 정렬했다.) 처음에는 모든 경우의 순열을 다 구했다. 그랬더니 메모리 초과가 나왔다..!! -예) 1번 사람이 카드 한 장, 2번 사람이 카드 한 장을 가진 경우라고 생각해보자. 사람들이 어..

[문제 보러 가기!](https://www.acmicpc.net/problem/17265 DFS로 풀었다. DFS에서 좌표, 그때까지 계산한 값, 연산자(그 직전이 연산자인 경우만)를 들고 다닌다. 학교에 도착하면(i==N-1 and j==N-1), 가능하다면 정답을 업데이트해준다. 아래, 오른쪽으로만 가라고 했으니까 그렇게 진행한다. 숫자일 때는 그 전의 연산자를 활용해서 계산해줬고, 연산자일 때는 숫자는 그대로 두고 그 연산자를 가지고 다음으로 넘겨주었다. 한 번 틀렸습니다.를 만났는데, 그 이유는 max_answer을 -1로 세팅하고 시작했기 때문이었다.. 처음에 0을 만나고 계속 -, 5, -, 5, -, 5, ... 이런 식으로 진행될 수도 있으니까 -1로 세팅하면 안되는 것이었다. 최대값을 구..

문제로 가기! 헐 ㅠㅠㅠㅠ 내가 이 문제를 풀다니ㅠㅠㅠ 나는 DP 문제는 식 생각하는 게 어려워서 좀 자신이 없다... 그래서 이 문제를 봤을 때도 '내가 풀 수 있을까?'하면서 봤다. 그래도 나름 종이에 끄적끄적하다보니 이런 식으로 DP 풀면 되겠다는 생각이 났다. 그리고 하나 하나 구현했더니 맞았습니다 !! 가 나왔다 ㅠㅠㅠ 코드를 쓰기 전에 미리 생각하는 게 중요한 것을 다시 한번 느꼈다 ! 접근 일단 천사 다리부터 시작하는 경우, 악마 다리부터 시작하는 경우를 나눠서 생각했다. 악마 다리에서 시작하는 예시를 가지고 설명하겠다. 일단 dp 테이블을 다 0으로 세팅하고 시작한다. dp 테이블은 3차원 리스트로 만들었다. 무슨 다리인지, 각 다리에서 몇 번째 돌인지, 마법 두루마리에서 몇번째 글자인지를..