본문 바로가기
반응형

PS/백준

 (318)
[BOJ] 백준 13909 창문 닫기 (Swift) 문제 https://www.acmicpc.net/problem/13909 13909번: 창문 닫기 서강대학교 컴퓨터공학과 실습실 R912호에는 현재 N개의 창문이 있고 또 N명의 사람이 있다. 1번째 사람은 1의 배수 번째 창문을 열려 있으면 닫고 닫혀 있으면 연다. 2번째 사람은 2의 배수 번째 www.acmicpc.net 풀이 창문이 열려있으려면 해당 수의 약수의 개수가 홀수개여야 합니다. 약수의 개수가 홀수개인 수는 제곱수 밖에 없습니다. ex) 1, 4, 9, 16.. n이하의 제곱수들의 개수를 출력해주면 되는 문제입니다. 소스코드 후기 창문이 열려있는 조건에 대해 생각해보고 풀 수 있었습니다.
[BOJ] 백준 15650 N과 M (2) (Swift) 문제 https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 풀이 1부터 n까지 자연수 중에서 중복없이, 오름차순 형태의 길이가 m인 수열을 모두 출력하는 문제입니다. https://dev-mandos.tistory.com/169 [BOJ] 백준 15649 N과 M (1) (Swift) 문제 https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복..
[BOJ] 백준 15649 N과 M (1) (Swift) 문제 https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 풀이 1부터 n까지 자연수 중에서 중복없이 m개를 고른 수열을 모두 출력하는 문제입니다. 백트래킹 알고리즘을 사용하여 풀 수 있습니다. 이미 뽑은 수는 제외하기 위해 visited라는 [Bool] 자료형을 사용하였습니다. 1부터 n까지 for문을 돌면서, 아직 선택하지 않은 수라면 배열에 넣어주고 visited 배열을 사용하여 선택했다는 표시를 해주고, 재귀함수 형태로 다시 1부터 n까지 ..
[BOJ] 백준 1004 어린왕자 (Swift) 문제 https://www.acmicpc.net/problem/1004 1004번: 어린 왕자 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 첫째 줄에 출발점 (x1, y1)과 도착점 (x2, y2)이 주어진다. 두 번째 줄에는 행성계의 개수 n이 주 www.acmicpc.net 풀이 출발점에서 도착점으로 이동하면서 행성에 진입하거나, 이탈할 때의 횟수를 구하는 문제입니다. 진입하거나 이탈할 때를 어떻게 알 수 있을까요? 먼저 출발점과 도착점을 그려봅시다. 아무런 행성이 없는 경우, 행성에 진입/이탈 할 필요가 없겠죠?? 다음 두 경우에도 행성에 진입/이탈 할 필요가 없을 것입니다. 다음과 같은 경우에 진입/이탈을 해야합니다. 행성이 출발점을 두르고있거..
[BOJ] 백준 1002 터렛 (Swift) 문제 https://www.acmicpc.net/problem/1002 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net 풀이 조규현의 좌표에서 류재명과의 거리가 주어졌을 때, 류재명이 있을 수 있는 좌표는 어디일까요? 류재명은 이 보라색 테두리에 모두 위치해(무한대) 있을 수 있습니다. 그렇다면 조규현과 백승환의 좌표가 모두 주어진 경우를 확인해 봅시다. 이러한 경우에는 류재명이 2군데로 체크된 곳에 위치해 있을 수 있습니다. 아하 그렇다면 두 원이 서로 다른 두 점에서 만난다면? 류재명이 있을 수 있는 좌표는 2개가 되겠군요. 류재명이 있을 수 있는 좌표가 1..
[BOJ] 백준 2477 참외밭 (Swift) 문제 https://www.acmicpc.net/problem/2477 2477번: 참외밭 첫 번째 줄에 1m2의 넓이에 자라는 참외의 개수를 나타내는 양의 정수 K (1 ≤ K ≤ 20)가 주어진다. 참외밭을 나타내는 육각형의 임의의 한 꼭짓점에서 출발하여 반시계방향으로 둘레를 돌면서 지 www.acmicpc.net 풀이 생각보다 어려웠던 문제입니다.. 단순히 큰 사각형에서 작은 사각형을 빼주면 답이 되는데, 작은 사각형의 넓이를 구하는것이 까다로웠습니다. 예시를 한번 그려서 살펴봅시다. 먼저 큰 사각형은 방향이 1번 등장한 것이 큰 사각형을 이루는 변이 됩니다. 4방향과 2방향이 되겠죠?? 그 뒤에 빨간색으로 쓴 (1, 60)과 (3, 20)이 작은 사각형의 넓이가 될 것입니다. 작은 사각형이 될것인..
[BOJ] 백준 3009 네 번째 점 (Swift) 문제 https://www.acmicpc.net/problem/3009 3009번: 네 번째 점 세 점이 주어졌을 때, 축에 평행한 직사각형을 만들기 위해서 필요한 네 번째 점을 찾는 프로그램을 작성하시오. www.acmicpc.net 풀이 직사각형이 되려면 동일한 x좌표가 2개씩이고 y좌표도 2개여야 합니다. 따라서 4번째 점은 x좌표는 3개의 좌표에서 x좌표가 1번 등장한 것의 x 좌표이고, y좌표는 3개의 좌표에서 y좌표가 1번 등장한 y 좌표입니다. 여러 방법이 있겠지만 저는 Dictionary를 사용해서, x좌표와 y좌표가 몇 번 등장했는지 count 해주고, 1번 등장한 좌표를 출력해주었습니다. 소스코드 후기 쉽게 풀 수 있는 문제입니다. 입출력을 보면 힌트를 얻을 수 있습니다. x좌표와 y좌..
[BOJ] 백준 1085 직사각형에서 탈출 (Swift) 문제 https://www.acmicpc.net/problem/1085 1085번: 직사각형에서 탈출 한수는 지금 (x, y)에 있다. 직사각형은 각 변이 좌표축에 평행하고, 왼쪽 아래 꼭짓점은 (0, 0), 오른쪽 위 꼭짓점은 (w, h)에 있다. 직사각형의 경계선까지 가는 거리의 최솟값을 구하는 프로그램 www.acmicpc.net 풀이 음.. 이런 문제는 직접 그려보면 이해가 빠릅니다. (6, 2) 에서 직사각형의 경계선까지 가는 거리는 상(1), 하(2), 좌(6), 우(4) 1이 최솟값입니다. 이는 상(h - y), 하(y), 좌(x), 우(w - x) 이렇게 나타낼 수 있겠네요. 이 중 가장 작은 값을 출력해주면 됩니다! 소스코드 후기 쉬운 문제이지만 이해가 잘 안간다면 직접 그려보면 쉽게 이..
반응형

티스토리툴바