1번 커플매칭 solve
문제
문제 설명
a, b, c, d 네 사람이 모여 커플 매칭 게임을 진행합니다.
커플 매칭 게임의 규칙은 다음과 같습니다.
- 커플 매칭 게임은 1개 이상의 라운드로 이루어져 있습니다.
- 참가자들은 매 라운드마다 커플이 되고 싶은 사람 한 명을 지목할 수 있습니다. 단, 직전 라운드에서 자신과 커플이 됐던 사람이나 자기 자신을 지목하면 규칙을 어기게 됩니다.
- 같은 라운드에서 두 사람이 서로를 지목한 경우에 커플이 됩니다. 단, 이번 라운드에서 규칙을 어긴 사람은 이번 라운드에서는 커플이 될 수 없습니다.
다음은 커플 매칭 게임을 3라운드까지 진행한 경우의 예시 입니다.
1라운드
a와 b가 서로를 지목했으므로 커플이 되었습니다.d는 자신을 지목했으므로 규칙을 어겼습니다.
2라운드
a, b, c의 선택이 모두 엇갈려 커플이 된 사람이 없습니다.그런데, 직전 라운드인 1라운드에서 a와 b가 커플이 됐는데도 a는 2라운드에서 다시 b를 지목하여 규칙을 어겼습니다.
3라운드
a와 b, c와 d 두 커플이 탄생하였습니다.a와 b는 1라운드에서 커플이 되었지만 직전 라운드인 2라운드에서는 커플이 안되었기 때문에 이번 라운드에서 커플이 될 수 있으며, 규칙을 어기지 않았습니다.
각 라운드의 게임 정보를 담고 있는 2차원 문자열 배열
rounds가 매개변수로 주어질 때, 참가자들이 규칙을 총 몇 번 어겼는지 return 하도록 solution 함수를 작성해주세요.제한사항
- 1 ≤
rounds의 길이 ≤ 20
rounds의 n번째 원소는 n번째 라운드를 의미합니다.rounds[i]는 4개의 원소를 가지고 있습니다.rounds[i]의 원소는"a","b","c","d"중의 하나입니다.rounds[i]의 첫 번째 원소는 a가 지목한 사람, 두 번째 원소는 b가 지목한 사람, 세 번째 원소는 c가 지목한 사람, 네 번째 원소는 d가 지목한 사람을 의미합니다.
입출력 예
입출력 예 설명
입출력 예 #1
문제의 예시와 같습니다.
a가 1번, b가 0번, c가 0번, d가 1번 규칙을 어겼으므로 규칙을 총 2번 어겼습니다.
입출력 예 #2
게임 결과는 다음과 같습니다.
1라운드
a와 b, c와 d가 서로를 지목하여 커플이 되었습니다.
2라운드
a와 b는 직전 라운드에 커플이 되었는데 다시 서로를 지목하여 규칙을 어겼습니다. 규칙을 어겼으므로 커플이 되지 않습니다.c와 d는 자기 자신을 지목했기 때문에 규칙을 어겼습니다.
a, b, c, d 모두 규칙을 1번씩 어겼으므로 규칙을 총 4번 어겼습니다.
입출력 예 #3
게임 결과는 다음과 같습니다.
1라운드
a와 b, c와 d가 서로를 지목하여 커플이 되었습니다.
2라운드
a와 d, b와 c가 서로를 지목하여 커플이 되었습니다.
3라운드
a와 b, c와 d가 서로를 지목하여 커플이 되었습니다.
a, b, c, d 모두 규칙을 어기지 않았으므로 규칙을 총 0번 어겼습니다.
입출력 예 #4
게임 결과는 다음과 같습니다.
1라운드
a와 d가 커플이 되었습니다.
2라운드
a와 c가 커플이 되었습니다.직전 라운드에서 a와 d가 커플이 되었는데 d가 a를 지목해서 규칙을 어겼습니다.
3라운드
a와 b가 커플이 되었습니다.직전 라운드에서 a와 c가 커플이 되었는데 c가 a를 지목해서 규칙을 어겼습니다.
a가 0번, b가 0번, c가 1번, d가 1번 규칙을 어겼으므로 규칙을 총 2번 어겼습니다.
2번 침대,테이블 배치 solve
설명
문제 설명
오늘의집 스토어에서 마음에 드는 침대들과 책상들을 찾았습니다. 이 중 침대와 책상을 하나씩 구매하고, 이들을 배치할 수 있는 가장 작은 면적의 직사각형 모양 방을 구하려 합니다.평면도상에서 방에 가구를 배치할 때 침대와 책상은
w × h 크기의 직사각형으로 표현하며, 그대로 배치하거나 90도 회전해서 배치할 수 있지만 서로 겹치는 부분이 없어야 합니다.예를 들어,
4×1 크기의 침대와
2×3 크기의 책상을 배치할 수 있는 방을 구한다고 가정합니다.
위 그림과 같이 4×4 크기의 방에 침대와 책상을 배치할 수 있습니다. 이때 방의 면적은 4×4=16입니다.
4×1 크기의 침대를 90도 회전할 경우 위 그림과 같이3×4크기의 방에 침대와 책상을 배치할 수 있습니다. 이때 방의 면적은 3 × 4 = 12 이며, 4×1 크기의 침대와 2 × 3 크기의 책상을 배치할 수 있는 방의 면적 중 최소입니다.
총예산이 최소가 되도록 침대와 책상, 그리고 방의 면적을 선택하려고 합니다. 이때 총예산은
침대의 가격 + 책상의 가격 + 방의 면적 × 방의 면적당 가격 으로 계산됩니다.침대들의 정보가 담긴 2차원 정수 배열
beds, 책상들의 정보가 담긴 2차원 정수 배열 tables, 방의 면적당 가격을 나타내는 정수 cost가 매개변수로 주어질 때, 가능한 총예산의 최솟값을 return 하도록 solution 함수를 완성해주세요.제한사항
- 1 ≤
beds의 길이 ≤ 1,000
beds의 원소는[w, h, price]형태입니다.w,h는 침대의 가로 길이와 세로 길이를 나타냅니다.- 1 ≤
w,h≤ 1,000 price는 침대의 가격을 나타냅니다.- 1 ≤
price≤ 1,000,000
- 1 ≤
tables의 길이 ≤ 1,000
tables의 원소는[w, h, price]형태입니다.w,h는 책상의 가로 길이와 세로 길이를 나타냅니다.- 1 ≤
w,h≤ 1,000 price는 책상의 가격을 나타냅니다.- 1 ≤
price≤ 1,000,000
- 1 ≤
cost≤ 10,000
입출력 예
beds | tables | cost | result |
[[4, 1, 200000]] | [[2, 3, 100000]] | 10000 | 420000 |
[[2, 3, 40], [2, 5, 20]] | [[1, 1, 30]] | 10000 | 80070 |
[[2, 3, 40000], [2, 5, 20000]] | [[1, 1, 30000]] | 10 | 50120 |
입출력 예 설명
입출력 예 #1
- 선택할 수 있는 침대와 책상이 하나씩 밖에 없으므로
4×1크기의 침대와2×3크기의 책상을 구매해야 합니다. 이 침대와 책상을 배치할 수 있는 방의 면적 중 최솟값은3×4=12이며, 문제의 예시와 같습니다.
- 따라서 총예산의 최솟값은
200000+100000+12×10000=420000입니다.
입출력 예 #2
- 총예산이 최소가 되기 위해서는 첫 번째 침대, 첫 번째 책상을 구매하고,
2×4크기의 방을 구해야 합니다.
- 총예산의 최솟값은
40+30+8×10000=80070입니다.
입출력 예 #3
- 총예산이 최소가 되기 위해서는 두 번째 침대, 첫 번째 책상을 구매하고,
2×6크기의 방을 구해야 합니다.
- 총예산의 최솟값은
20000+30000+12×10=50120입니다.
반b정도 통과
- 올통과
3번 가능한 배치 경우의 수 ⇒ 시도했으나 아예 못 품
문제 설명
오늘의집을 통해 집을 인테리어 하기 전에 집을 설계하려고 합니다.
n x m 크기의 비어있는 집이 주어집니다. 당신은 이 집에 방과 화장실을 배치하려고 합니다.방은 항상 2 x 2의 정사각형 모양이며 화장실은 항상 1 x 2의 직사각형 모양입니다.예를 들어, 아래처럼 4 x 5 크기의 비어있는 집이 있다고 합시다.
당신은 이 집에 방
room개와 화장실 bath개를 배치하려고 합니다.단, 방과 화장실을 배치할 때 세 가지 주의할 점이 있습니다.첫째, 방과 화장실을 배치할 때 방과 화장실은 상하좌우 중 최소 한 방향으로 집의 빈 공간과 인접해 있어야 합니다. 즉, 집의 어느 빈 공간에서도 이어진 집의 빈 공간을 통해 모든 방과 화장실에 들어갈 수 있어야 합니다.아래 그림과 같이 방과 화장실을 배치할 경우, 왼쪽 아래 방을 제외하고 모든 방과 화장실은 집의 빈 공간과 인접해 있어서 접근이 가능하지만 왼쪽 아래 방은 방과 화장실로 둘러싸여서 접근할 수 없습니다. 방과 방, 방과 화장실, 화장실과 화장실 사이의 이동은 불가능합니다. 방이나 화장실로 이동은 인접한 집의 빈 공간에서만 할 수 있습니다.
둘째, 방과 화장실을 배치하고 남은 집의 빈 공간은 하나로 연결되어 있어야 합니다. 즉, 방과 화장실을 배치할 때 집에서 버려지는 공간이 있으면 안 됩니다.아래 그림과 같이 방과 화장실을 배치할 경우, 집의 가운데 통로로 3개의 방과 화장실에 접근할 수 있지만, 집의 오른쪽 아래 부분은 가운데 부분과 연결되어 있지 않아 버려지는 공간이 됩니다.
셋째, 집의 입구를 설치하기 위해 방과 화장실을 배치하고 남은 집의 빈 공간 중 최소 한 공간은 집의 테두리와 인접해 있어야 합니다.아래 그림과 같이 방과 화장실을 배치할 경우, 첫 번째와 두 번째 규칙은 만족했지만 집의 테두리에 전부 방과 화장실이 있어서 집의 입구를 설치할 공간이 없어 세 번째 규칙은 만족하지 못했습니다.
집의 세로 길이를 나타내는 정수
n, 집의 가로 길이를 나타내는 정수 m, 배치해야 할 방의 개수를 나타내는 정수 room, 배치해야 할 화장실의 개수를 나타내는 정수 bath가 매개변수로 주어집니다. 위 세 가지 조건에 맞게 방과 화장실을 배치하는 방법의 수를 return 하도록 solution 함수를 완성해주세요. 단, 모든 방과 화장실을 배치할 수 없는 경우 0을 return 해주세요.제한사항
- 1 ≤
n,m≤ 5
- 1 ≤
room,bath≤ 3
입출력 예
입출력 예 설명
입출력 예 #1
아래 그림은 방과 화장실을 조건에 맞게 배치한 예시 중 일부입니다.
4 x 5 크기의 집에 방 3개, 화장실 1개를 조건에 맞게 배치하는 방법의 수는 20가지입니다.따라서 20을 return 해야 합니다.
입출력 예 #2
아래 그림과 같이 방과 화장실을 배치할 경우, 집의 빈 공간이 없어지게 됩니다. 따라서, 첫 번째, 두 번째, 세 번째 조건에 모두 맞지 않습니다.
2 x 3 크기의 집에 방 1개, 화장실 1개를 조건에 맞게 배치하는 방법은 없습니다.따라서 0을 return 해야 합니다.
입출력 예 #3
아래 그림은 방과 화장실을 배치한 예시 중 일부입니다.
- 첫 번째 집은 왼쪽 위의 방에 접근할 수가 없습니다. 첫 번째 조건에 맞지 않습니다.
- 두 번째 집은 집의 빈 공간끼리 연결되어 있지 않습니다. 두 번째 조건에 맞지 않습니다.
- 세 번째 집은 오른쪽 위의 방에 접근할 수가 없습니다. 첫 번째 조건에 맞지 않습니다.
3 x 4 크기의 집에 방 2개 화장실 1개를 조건에 맞게 배치하는 방법은 없습니다.따라서 0을 return 해야 합니다.
입출력 예 #4
아래 그림은 방과 화장실을 조건에 맞게 배치한 모든 방법입니다.
2 x 4 크기의 집에 방 1개, 화장실 1개를 조건에 맞게 배치하는 방법의 수는 6가지입니다.따라서 6을 return 해야 합니다.