live the life you love

www.acmicpc.net/problem/20168 20168번: 골목 대장 호석 - 기능성 첫 줄에 교차로 개수 N, 골목 개수 M, 시작 교차로 번호 A, 도착 교차로 번호 B, 가진 돈 C 가 공백으로 구분되어 주어진다. 이어서 M 개의 줄에 걸쳐서 각 골목이 잇는 교차로 2개의 번호와, 골목의 www.acmicpc.net 다익스트라 문제를 풀려고 했는데, 백트래킹으로 풀었다. 처음에는 문제의 설명이 조금 헷갈렸는데, 고려해야할 조건은 다음과 같았다. 가진 돈을 목적지까지 도착하기 전에 전부 사용하지 않기 목적지에 도착했다면 지금까지 지나온 노드 중 가장 비용이 큰 값이 어떤 것인가? 목적지에 도착하는 길이 2개 이상인 경우 가장 비용이 큰 값 중 최소가 정답 위의 조건들을 백트래킹에 맞게 풀어주..

www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 문제를 잘 읽자! 문제를 잘 못 읽어서 1시간을 고민하다가 질문검색을 통해 코드를 보고 문제를 잘못 읽은것을 깨달았다. 테트로미노 "하나"를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오. 주어진 종이에 여러 종류의 테트로미노를 놓고 그 중에 최대를 구하는 것이 아니다. 최대 500x500 크기의 종이에 테트로미노 1개를 놓고 놓인 부분의 합이 최대가 되는 것을 ..

문제의 조건은 간단했지만 dp와 dfs가 합쳐진 문제였다. 처음에 dp같지 않은 dp를 사용했더니 시간초과가 발생했다. dp[i][j]의 값을 i,j 위치에 판다가 있을 경우, 살 수 있는 최대일수 로 설정하였다. dfs의 탈출 조건을 설정해주는게 중요하다고 생각한다. if (dp[y][x] != 0) return dp[y][x]; dp[y][x]가 0이 아니라는 것은 해당 위치에 판다가 놓여졌을 때 살 수 있는 최대일수가 결정되었다는 뜻이다. 그러므로, [y][x]위치에 방문을 하였을 때 살 수 있는 일수를 계산하지 않고 그 값을 사용하면 되는 것이다. 소스코드 #include #include #define endl "\n" #define MAX 500 #define pii pair using name..

https://www.acmicpc.net/problem/1987 1987번: 알파벳 문제 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 www.acmicpc.net 백트래킹을 연습하기 위해 약 1달전, 2월 4일에 풀었을 때 틀렸던 문제를 다시 풀어보았다. 그때 트렐로에 남겨둔 메시지는 이랬었다. 두가지..