Code/BOJ
-
#1917 정육면체 전개도Code/BOJ 2020. 1. 2. 19:37
출처:https://www.acmicpc.net/problem/1917 1917번: 정육면체 전개도 세 개의 입력 데이터가 주어지며, 각각의 입력 데이터는 여섯 개의 줄로 이루어져 있다. 각 데이터는 여섯 개의 줄에 걸쳐 여섯 개의 숫자가 빈 칸을 사이에 두고 주어진다. 숫자는 0 또는 1로 이루어지며, 36개의 숫자 중 1은 정확히 6개가 있다. 0은 공백을 나타내며 1은 정사각형을 나타낸다. (즉 전체의 그림이 전개도를 나타낸다고 보면 된다.) 정사각형들이 서로 떨어져 있는 경우는 없다. www.acmicpc.net 시뮬레이션 문제다. 먼저 처음에 정육면체의 전개도를 펼치면 일직선인 정사각형 4개과 그 큰 변을 기준으로 양 옆에 하나씩 붙어있는 전개도가 정육면체 전개도의 전부라고 생각해서 틀렸다.(아..
-
#2098 외판원 순회Code/BOJ 2020. 1. 1. 20:28
출처:https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다. 항상 순회할 수 있는 경우만 입력으로 주어진다. www.acmicpc.net 외판원 순회는 세계일주 라고 생각하면 된다. 한국에서 출발하는데 가고싶은 나라가 프랑스 독일 영국이라면 한국에서 출발해서 어떻게 나라를 거쳐가서 돌아올때가 가장 경비가 저렴한지의 느낌으로 풀어주면 된다. 이 문제는 비트마스킹을 이용하여 메모이제이션을 활용한 dp문제이다. 만약 ..
-
#14267 내리 갈굼Code/BOJ 2020. 1. 1. 19:43
출처: https://www.acmicpc.net/problem/14267 14267번: 내리 갈굼 영선회사에는 치명적인 악습이 있는데, 바로 상사가 직속 부하를 갈구면 그 부하가 부하의 직속 부하를 연쇄적으로 갈구는 내리 갈굼이 있다. 즉, 상사가 한 직속 부하를 갈구면 그 부하의 모든 부하들이 갈굼을 당한다. 갈굼에 대해 정도에 대한 수치가 주어지는데, 이 수치 또한 부하들에게 똑같이 갈궈진다. 직속 상사와 직속 부하관계에 대해 주어지고, 갈굼에 대한 정보가 주어질 때, 각자 얼마의 갈굼을 당했는지 출력하시오, www.acmicpc.net 번호가 작을수록 상사이고 노드(직원)끼리 직속 상관관계인 간선을 벡터로 연결한 후에 1번부터 n번 직원까지 갈굼의 정도를 출력하는 문제이다. 처음에는 간선 연결 후..
-
#1019 책 페이지Code/BOJ 2019. 12. 31. 22:46
n이 34라고 하자. 그렇다면 10쪽부터 29쪽까지는 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 1의 자리에서 0부터 9까지 2번 즉 29의 2와 10의 1을 빼준 2-1+1 개씩 나오게 된다. 즉 1부터 9까지 각 숫자의 갯수의 합, 34,33,32,...,29까지 숫자의 갯수의 합을 구해주고 나머지는 위의 방식대로 적용하면된다. 자릿수를 높여서 생각해보자 n=341이다. 먼저 마찬가지로 1부터 9까지 각 숫자의 갯수의 합, 341,340까지는 cal함수를 통해 수동으로 계산을 한다. 10쪽부터 339쪽까지는 조금 수의 모양을 바꿔 010쪽부터(맨 앞에 붙여준 0은 그냥 자릿수만 맞춰주는 0이며 아무 의미 없다.) 339쪽까지 1의자리에서..
-
#1713 후보 추천하기Code/BOJ 2019. 12. 31. 22:28
출처: https://www.acmicpc.net/problem/1713 1713번: 후보 추천하기 첫째 줄에는 사진틀의 개수 N이 주어진다. (1≤N≤20) 둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸을 사이에 두고 추천받은 순서대로 주어진다. 총 추천 횟수는 1,000번 이하이며 학생을 나타내는 번호는 1부터 100까지의 자연수이다. www.acmicpc.net 문제에서 친절하게 알고리즘 설계도를 줬다. 해당 상세 구현 설명을 기준으로 문제를 조금 재해석해서 내 맞춤으로 다시한번 수정해 보았다. 먼저 문제는 학생의 사진을 게시할 수 있는 정해진 사진틀이 있고 추천할때마다 항상 추천한 그 학생의 사진은 사진틀에 걸려야 한다. 이 과정에서 문제와..
-
#2933 미네랄Code/BOJ 2019. 12. 31. 22:05
출처: https://www.acmicpc.net/problem/2933 2933번: 미네랄 문제 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄이 저장되어 있으며, 던진 막대기가 미네랄을 파괴할 수도 있다. 동굴은 R행 C열로 나타낼 수 있으며, R×C칸으로 이루어져 있다. 각 칸은 비어있거나 미네랄을 포함하고 있으며, 네 방향 중 하나로 인접한 미네랄이 포함된 두 칸은 같은 클러스터이다. 창영은 동굴의 왼쪽에 www.acmicpc.net 문제에서 요구하는 사항을 구현하는 단순 구현 문제이다. 하지만 구현이 요소에 1.미네랄 깨기, 2. 그룹생성하기, 3.떠 있는 그룹..
-
#2213 트리의 독립집합Code/BOJ 2019. 12. 30. 09:40
출처: https://www.acmicpc.net/problem/2213 2213번: 트리의 독립집합 첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 가중치이다(1 ≤ i ≤ n). 셋째 줄부터 마지막 줄까지는 에지 리스트가 주어지는데, 한 줄에 하나의 에지를 나타낸다. 에지는 정점의 쌍으로 주어진다. 입력되는 정수들 사이에는 콤마가 없고 대신 빈칸이 하나 혹은 그 이상 있다. 가중치 www.acmicpc.net 트리의 독립집합을 구하는 문제인데 연결 돼 있는 정점 또는 노드들을 연속으로 선택하지 않으면 되는 문제이다. 재귀를 활용한..
-
#1102 발전소Code/BOJ 2019. 12. 30. 09:09
출처: https://www.acmicpc.net/problem/1102 1102번: 발전소 은진이는 발전소에서 근무한다. 은진이가 회사에서 잠깐 잘 때마다, 몇몇 발전소가 고장이난다. 게다가, 지금 은진이의 보스 형택이가 은진이의 사무실로 걸어오고 있다. 만약 은진이가 형택이가 들어오기 전까지 발전소를 고쳐놓지 못한다면, 은진이는 해고당할 것이다. 발전소를 고치는 방법은 간단하다. 고장나지 않은 발전소를 이용해서 고장난 발전소를 재시작하면 된다. 하지만, 이때 비용이 발생한다. 이 비용은 어떤 발전소에서 어떤 발전소를 재시작하느냐에 따라 다르다 www.acmicpc.net 비트마스킹와 메모이제이션을 활용한 문제 켜져있는 발전소들을 기준으로 계속해서 꺼져있는 발전소을 가동시켜야 하는 문제이며 꺼져있던 발..