개발조아

문제 링크 : https://www.acmicpc.net/problem/9202 9202번: Boggle 각각의 Boggle에 대해, 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 개수를 출력한다. 한 Boggle에서 같은 단어를 여러 번 찾은 경우에는 한 번만 찾은 것으로 센다. 가장 긴 단어가 여러 개 www.acmicpc.net 트라이와 DFS를 사용해서 풀었다. 단어 사전에 단어가 최대 30만개 이므로 검색 시 오래 걸릴 것이다. 그래서 트라이로 단어 사전을 재구성하자. 트라이의 노드는 현재 글자, 자식, 단어의 끝 상태 3가지로 구성했다. 단어의 끝은 해당 글자로 끝나는 단어가 있다면 True로 설정했다. 그리고 boggle의 모든점에서 DFS를 실행하자. 이때 트라이도 함께 가져가자...

문제 링크 : https://www.acmicpc.net/problem/7682 7682번: 틱택토 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 줄은 9개의 문자를 포함하며, 'X', 'O', '.' 중 하나이다. '.'은 빈칸을 의미하며, 9개의 문자는 게임판에서 제일 윗 줄 왼쪽부터의 순서이다. 입 www.acmicpc.net 처음에는 그냥 단순하게 모든 경우를 재귀로 구해서 set에 저장 후 set에 있냐 없냐로 검사했다. 당연히 느리다. 다른 분들이 비해서 느려서 다시 풀어봤다. 모두 구하지 말고 입력으로 들어온 문자를 검사를 하는 것으로 했다. 게임의 종료 조건은 가로,세로,대각으로 3개의 말이 모이면 된다. 그래서 if문으로 다 해줬다. 그리고 모든 칸이 다 채워졌는데도 위의 조건이 ..

문제 링크 : https://www.acmicpc.net/problem/19942 19942번: 다이어트 식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다. 아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택해서 이들의 영양분의 각 www.acmicpc.net 브루트포스 문제이다. 재귀로도 할수 있겠지만 파이썬은 이미 아주 훌륭한 조합를 제공한다. 1개,2개,n개까지 뽑는 조합을 다 만들어서 조건을 만족시키고 합이 최소가 되는 것을 찾아서 출력했다. 그리고 중간이 합이 같다면 사전순으로 앞선것이 와야한다. 그래서 두개를 하나의 튜플로 만들어 정렬하고 앞에것을 저장했다. from sys import stdin from itertools i..

문제 링크 : https://www.acmicpc.net/problem/20165 20165번: 인내의 도미노 장인 호석 사람을 화나게 하는 법은 다양하다. 그 중에서도 악질은 바로 열심히 세워놓은 도미노를 넘어뜨리는 것이다. 이번에 출시된 보드 게임인 "너 죽고 나 살자 게임"은 바로 이 점을 이용해서 2명이 www.acmicpc.net 어렵지 않은 시뮬레이션 문제이다. 나는 큐와 도미노의 상태와 도미노의 높이를 나타낼 배열을 사용했다. 공격 알고리즘은 아래와 같다. 도미노를 쓰러트릴때 일단 시작 좌표를 큐에 넣는다. 그리고 큐가 빌때까지 아래 동작을 수행한다. 1. 큐에서 좌표를 빼고 현재점은 쓰러트리는 점이므로 score를 +1 해준다. 2. 시작 좌표 도미노의 높이-1 만큼 해당 방향으로 도미노를..

문제 링크 : https://www.acmicpc.net/problem/4577 4577번: 소코반 소코반은 1982년에 일본에서 만들어진 게임으로, 일본어로 창고지기라는 뜻이다. 이 게임은 캐릭터를 이용해 창고 안에 있는 박스를 모두 목표점으로 옮기는 게임이다. 목표점의 수와 박스의 수 www.acmicpc.net 요구하는 사항이 어렵지는 않지만 체크해줘야할 게 많은 문제이다. 졸려서 문제를 대충 읽었다가 몇번 틀렸다. 캐릭터가 이동하는 방향이 .이거나+ 라면 그대로 이동하면 된다. 근데 b 라면 다음칸도 확인해서 .이거나+ 라면 캐릭터와 블록을 각 한칸씩 이동한다. 만약 박스를 목표지점에 다 넣었을 때는 다음 명령은 무시해도된다. 모든 명령을 수행후 결과를 출력하면 된다. 요구사항은 적다. 근데 캐릭..

문제 링크 : https://www.acmicpc.net/problem/1662 1662번: 압축 압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이 www.acmicpc.net 문제 설명이 너무 없었다. 예제를 보고 설명하면 아래와 같다. 입력 예제 1: 33(562(71(9))) 압축은 K(Q)형태로 되어 있다. K는 한자리 이므로 K와 Q를 구분하면 아래와 같을 것이다. 3 3(56 2(7 1(9))) 가장 안쪽 7 1(9)을 보자 K는1 Q는 9이므로 9가 될 것이고 앞의 7과 합쳐져 79가 된다. 그다음으로 가면 56 2(79)가 되고 79를 ..

문제 링크 : https://www.acmicpc.net/problem/1162 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로가 연결하는 두 도시와 도로를 통과하 www.acmicpc.net 처음 풀이가 맞았는데 오타 때문에 지우고 다시 풀다가 오타를 발견하고 원래코드로 돌아와 푼 바보같은 문제였다. 하지만 결국 시간초과랑 싸운 문제이다. 알고리즘은 간단하다. 우선 최단경로를 구해야하므로 다익스트라를 사용했다. 그리고 각 노드를 방문했을 때의 상태가 달라야한다. 상태는 도로를 포장한 개수이다. 다음 도로를 포장하고 갈지 아니면 그냥 갈..

문제 링크 : https://www.acmicpc.net/problem/1719 1719번: 택배 명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하 www.acmicpc.net 문제에 모든 노드가 다 연결되어 있는지 만약 아니라면 그때의 출력은 어찌하는지가 없었다. 그래서 그냥 모든 노드가 연결되어 있다는 가정하에 문제를 풀었다. 나는 플로이드 와샬로 풀었다. 노드가 최대 200개 이므로 충분히 해결할 수 있다. 우선 인접 행렬로 구성했다. 배열[a][b] = [b,c] a->b로 가는 최단 경로중 b를 가장 먼저 들러야하고 비용은 c이다 는 의미이다. 처음 입력은..