noj.am/2873 2873번: 롤러코스터 첫째 줄에 가장 가장 큰 기쁨을 주는 롤러코스터는 가장 왼쪽 위 칸부터 가장 오른쪽 아래 칸으로 어떻게 움직이면 되는지를 출력한다. 위는 U, 오른쪽은 R, 왼쪽은 L, 아래는 D로 출력한다. 정답 www.acmicpc.net 재밌는 문제다. 당연히 최대한 많은 칸을 지나야 제일 좋은데, 체스판을 생각해보면 모든 칸을 지나며 맨 위 왼쪽 끝에서 맨 아래 오른쪽끝으로 모든 칸을 지나며 갈 수가 없다. 그래서 딱 한칸을 빼고 모두 지나야 하는데, 그 칸은 당연히 점수가 제일 낮은 칸일거고, 조금 고민해보면 어느 칸을 안지날 수 있는지 알 것이다. 칸이 다 똑같은게 아니라 이 칸을 안지나게 된다면 한칸만 안지나고 경로를 그릴수가 없는 칸이 있다. 그래서 그거랑 최소..
noj.am/1294 1294번: 문자열 장식 첫째 줄에 단어의 개수 N이 주어진다. N은 최대 20이다. 둘째 줄부터 N개의 줄에 단어가 주어진다. 단어는 최대 1,000글자이고, 공백은 없이 알파벳 대문자로만 구성되어 있다. www.acmicpc.net 첨엔 포인터를 써야하나 생각했지만 그냥 벡터에 문자열 담아놓고 쓴 글자를 지우는 방식을 사용하기로 했다. v[j].erase(v[j].begin()); erase라니,, 이게 C++? 또 substr 메소드로 첫 글자가 같을때 추가 비교를 해주었고, 느릴것 같았으나 128ms로 가뿐히 통과했다. 맞힌 사람 들어가보니 0ms도 있던데 이건 어떻게 한거지.. 질문 들어가서 좀 읽어보니까 pq써서 하면 편하고 빠르게 할 수 있을지도? 매번 substr 따는..
요즘 새로운 DP 방법들 찾아보면서 뭔가 알아야 되는거도 많아지고 해서 정리도 할겸 DP문제 푸는걸 정리해서 올려보고 싶었다. 겨울에 열심히 DP 파면서 어려운 문제도 4~5시간씩 써가며 풀었는데 3월되서는 3개는 풀었나? 싶어서 DP 푸는걸 기록해볼거다. 난이도 있는 백준(또는 정올)문제랑 내가 생각했던 간단한 풀이를 같이 남겨 나중에 보기도 편하게 하고, 아이디어랑 이런건 따로 더 쓸거다. 난이도는 한 골드 상위에서 플래, 다이아까지 공부할거다. DP말고도 그리디나 자료구조 일지도 쓰고싶은데 그건 시간될때.. 일단 겨울에 푼 어려웠던 문제 하나 noj.am/2647 2647번: 검은점과 하얀점 연결 2n개의 점이 x축의 좌표 1,2,...2n에 놓여 있다. 그 중 n개는 검은 점이고, n개는 하얀 점..